盛日辉的博客
0%

蓝桥-DP练习

发表于 更新于 分类于 ，

李白打酒加强版

https://www.lanqiao.cn/problems/2114/learning/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# n酒店，m花
n, m = map(int, input().split())
dp = [[[0 for k in range(m + 1)] for j in range(m + 1)] for i in range(n + 1)]
# dp[i][j][k] 遇到i个酒店j个花后剩余k酒量的方案数
dp[0][0][2] = 1
# dp[1][0][4] = 1
# dp[0][1][1] = 1
# dp[0][2][0] = 1

for i in range(0, n + 1):
    for j in range(0, m + 1):
        for k in range(m + 1):
            if j == m and i != n:  # 不能没花了但酒店还有
                continue
            if not k & 1 and i > 0:  # 现在这一个是酒店，i减1，k是一半
                dp[i][j][k] += dp[i - 1][j][k // 2]
            if k != m and j > 0:
                dp[i][j][k] += dp[i][j - 1][k + 1]

print(dp[n][m][0] % 1000000007)
  1. 酒的减少量是一样的，都是m

开心的金明

https://www.lanqiao.cn/problems/554/learning/

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n, m = map(int, input().split())  # 价钱，物品数量
v = [0]  # 价格
p = [0]  # 重要度
for i in range(m):
    vv, pp = map(int, input().split())
    v.append(vv)
    p.append(pp)

dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(n + 1):
        if j < v[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i] * p[i])
print(dp[m][n])

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
n, m = map(int, input().split())  # 价钱，物品数量
v = [0]  # 价格
p = [0]  # 重要度
for i in range(m):
    vv, pp = map(int, input().split())
    v.append(vv)
    p.append(pp)

dp = [0] * (n + 1)
for i in range(1, m + 1):
    for j in range(n, v[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - v[i]] + v[i] * p[i])
print(dp[-1])