今日概览

今天记录了 6 道题。

题号	题目	状态	语言	标签
P1060	[NOIP 2006 普及组] 开心的金明	AC	Python	动态规划、背包DP
P1802	5 倍经验日	AC	Python	动态规划、背包DP
P1049	[NOIP 2001 普及组] 装箱问题	AC	Python	动态规划
P1048	[NOIP 2005 普及组] 采药	AC	Python	-
P1470	[IOI 1996 / USACO2.3] 最长前缀 Longest Prefix	AC	Python	动态规划
P2858	[USACO06FEB] Treats for the Cows G/S	AC	Python	区间DP

刷题记录

P1060 [NOIP 2006 普及组] 开心的金明

• 题目：[NOIP 2006 普及组] 开心的金明
• 状态：AC
• 语言：Python
• 标签：动态规划、背包DP

题目原文

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $N$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1-5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第 $j$ 件物品的价格为 $v_j$，重要度为 $w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,…,j_k$，则所求的总和为： $v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2} …+v_{j_k} \times w_{j_k}$ 请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为 $2$ 个正整数，用一个空格隔开：$n,m$（$n

输出格式

$1$ 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（$

说明/提示

NOIP 2006 普及组 第二题

代码

v = []
w = []
s = []
for _ in range(m):
    a,b = map(int,input().split())
    v.append(a)
    w.append(b)
    s.append(a*b)
memo = {}
def satisfaction(v,s,n):
    num = len(v)
    dp = [0]*(n+1)
    for i in range(num):
        if v[i] <= n:
            for j in range(n,v[i]-1,-1):
                if j in memo:
                    dp[j] = memo[j]

                if j-v[i] in memo:
                    dp[j-v[i]] = memo[j-v[i]]
                dp[j] = max(
                    dp[j],dp[j-v[i]]+s[i]
                )

                memo[j] = dp[j]


    return dp[n]

print(satisfaction(v,s,n))

P1802 5 倍经验日

• 题目：5 倍经验日
• 状态：AC
• 语言：Python
• 标签：动态规划、背包DP

题目原文

题目描述

现在 absi2011 拿出了 $x$ 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。 由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 $2$ 个药去打别人，别人却表明 $3$ 个药才能打过，那么相当于你输了并且这两个属性药浪费了。 现在有 $n$ 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。 要求求出最大经验 $s$，输出 $5s$。

输入格式

第一行两个数，$n$ 和 $x$。 后面 $n$ 行每行三个数，分别表示失败时获得的经验 $\mathit{lose}_i$，胜利时获得的经验 $\mathit{win}_i$ 和打过要至少使用的药数量 $\mathit{use}_i$。

输出格式

一个整数，最多获得的经验的五倍。

说明/提示

【Hint】 五倍经验活动的时候，absi2011 总是吃体力药水而不是这种属性药。 【数据范围】

• 对于 $10\%$ 的数据，保证 $x=0$。

• 对于 $30\%$ 的数据，保证 $0\le n\le 10$，$0\le x\le 20$。

• 对于 $60\%$ 的数据，保证 $0\le n,x\le 100$， $10

代码

n,x = map(int,input().split())
lose = []
win = []
use = []
for _ in range(n):
    l,w,u = map(int,input().split())
    lose.append(l)
    win.append(w)
    use.append(u)

def max_s(lose,win,use,n,x):
    dp = [0]*(x+1)
    for i in range(n):
        if use[i] <= x:
            for j in range(x,use[i]-1,-1):
                
                dp[j] = max(
                    dp[j]+lose[i],dp[j-use[i]]+win[i]
                )
        else:
            dp[j] = dp[j] + lose[i]
    
    s = dp[x]
    return s

print(5*max_s(lose,win,use,n,x))

复盘

注意药水不够可以选择输，输也会获得经验。另外，本题中dp数组本身就起到记忆的作用，所以不需要memo，meo一般用于递归函数中。

P1049 [NOIP 2001 普及组] 装箱问题

• 题目：[NOIP 2001 普及组] 装箱问题
• 状态：AC
• 语言：Python
• 标签：动态规划

题目原文

题目描述

有一个箱子容量为 $V$，同时有 $n$ 个物品，每个物品有一个体积。 现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 $V$，表示箱子容量。 第二行共一个整数 $n$，表示物品总数。 接下来 $n$ 行，每行有一个正整数，表示第 $i$ 个物品的体积。

输出格式

• 共一行一个整数，表示箱子最小剩余空间。

说明/提示

对于 $100\%$ 数据，满足 $0

代码

V = int(input())
n = int(input())
v = []
for _ in range(n):
    v.append(int(input()))

def max_v(V,n,v):
    dp = [0]*(V+1)
    for i in range(n):
        for j in range(V,v[i]-1,-1):
            dp[j]=max(
                dp[j],dp[j-v[i]]+v[i]
            )

    return dp[V]

print(V-max_v(V,n,v))

P1048 [NOIP 2005 普及组] 采药

• 题目：[NOIP 2005 普及组] 采药
• 状态：AC
• 语言：Python

题目原文

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。 接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

说明/提示

【数据范围】

• 对于 $30\%$ 的数据，$M \le 10$；

• 对于全部的数据，$M \le 100$。 【题目来源】 NOIP 2005 普及组第三题

代码

T,M = map(int,input().split())
t = []
v = []
for _ in range(M):
    a,b = map(int,input().split())
    t.append(a)
    v.append(b)

def max_value(T,M,t,v):
    dp = [0]*(T+1)
    for i in range(M):
        for j in range(T,t[i]-1,-1):
            dp[j] = max(
                dp[j],dp[j-t[i]]+v[i]
            )

    return dp[T]

print(max_value(T,M,t,v))

P1470 [IOI 1996 / USACO2.3] 最长前缀 Longest Prefix

• 题目：[IOI 1996 / USACO2.3] 最长前缀 Longest Prefix
• 状态：AC
• 语言：Python
• 标签：动态规划

题目原文

题目描述

在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列（即元素）很感兴趣。 如果一个集合 $P$ 中的元素可以串起来（元素可以重复使用）组成一个序列 $S$，那么我们认为序列 $S$ 可以分解为 $P$ 中的元素。元素不一定要全部出现（如下例中 BBC 就没有出现）。举个例子，序列 ABABACABAAB 可以分解为下面集合中的元素：{A,AB,BA,CA,BBC}。 序列 $S$ 的前面 $k$ 个字符称作 $S$ 中长度为 $k$ 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，设 $S'$ 是序列 $S$ 的前缀，使其可以分解为给出的集合 $P$ 中的元素，求 $S'$ 的长度 $k$ 的最大值。

输入格式

输入数据的开头包括若干个元素组成的集合 $P$，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 . 的行，集合中的元素没有重复。 接着是大写字母序列 $S$，用字符串表示，每 $76$ 个字符换一行。

输出格式

只有一行，输出一个整数，表示 $S$ 符合条件的前缀的最大长度。

说明/提示

【数据范围】 对于 $100\%$ 的数据，$1\le \text{card}(P) \le 200$，$1\le |S| \le 2\times 10^5$，$P$ 中的元素长度均不超过 $10$。 翻译来自 NOCOW。

思路

用dp数组储存第i位是否能用P凑出。

代码

import sys
P = []
S = ''
while True:
    line = sys.stdin.readline().split()
    if line == ['.']:
        break
    P += line

while True:
    line = sys.stdin.readline().strip()
    if line == '':
        break
    S += line

def max_len(P,S):
    dp = [False]*(len(S)+1)
    dp[0] = True

    for i in range(len(S)+1):
        if dp[i] == True:

            for p in P:
                if S[i:i+len(p)] == p:
                    dp[i+len(p)] = True
    
    j = len(S)
    while dp[j] == False:
        j-=1
    return j

print(max_len(P,S))

P2858 [USACO06FEB] Treats for the Cows G/S

• 题目：[USACO06FEB] Treats for the Cows G/S
• 状态：AC
• 语言：Python
• 标签：区间DP

题目原文

题目描述

约翰经常给产奶量高的奶牛发特殊津贴，于是很快奶牛们拥有了大笔不知该怎么花的钱。为此，约翰购置了 $N$（$1 \leq N \leq 2000$）份美味的零食来卖给奶牛们。每天约翰售出一份零食。当然约翰希望这些零食全部售出后能得到最大的收益，这些零食有以下这些有趣的特性： + 零食按照 $1, \ldots, N$ 编号，它们被排成一列放在一个很长的盒子里。盒子的两端都有开口，约翰每天可以从盒子的任一端取出最外面的一个。 + 与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃。当然，这样约翰就可以把它们卖出更高的价钱。 + 每份零食的初始价值不一定相同。约翰进货时，第 $i$ 份零食的初始价值为 $V_i$（$1 \leq V \leq 1000$）。 + 第 $i$ 份零食如果在被买进后的第 $a$ 天出售，则它的售价是 $V_i \times a$。 $V_i$ 表示的是从盒子顶端往下的第 $i$ 份零食的初始价值。约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱。

输入格式

第一行一个正整数 $N$。 接下来 $2 \sim N+1$ 行，第 $i+1$ 行为一个正整数 $V_i$。

输出格式

一行一个整数表示答案。

说明/提示

样例的最优解是：按 $1 \to 5 \to 2 \to 3 \to 4$ 的顺序卖零食，得到的钱数是 $1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 1 + 5 \times 5 = 43$。

思路

区间DP本质是小区间->大区间，所以一般需要按区间长度从小到大进行枚举

代码

v = []
N = int(input())
for _ in range(N):
    v.append(int(input()))

def day(N,l,r) :
    return N - r + l

def most(v,N):
    dp = [[0]*(N) for _ in range(N)]

    l = 0
    r = N-1

    for length in range(1, N + 1):
        for l in range(0, N - length + 1):
            r = l + length - 1
            if l == r:
                dp[l][r] = v[l] * N
            else:
                d = day(N, l, r)
                dp[l][r] = max(
                    dp[l + 1][r] + v[l] * d,
                    dp[l][r - 1] + v[r] * d
                )
    return dp[0][N-1]

print(most(v,N))