A18734. 条形蛋糕
填空题
困难
知识点
题目描述
条形蛋糕
题目描述
寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。
小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？
有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算用这个问题考一考小杨同学，问题如下：
给定一条长度为 的长条蛋糕和一个价格表，该价格表表示长度为 i（i= 1,2,...,n）的蛋糕块的价格为 pi 。求蛋糕的分割方案，使得总销售价格最大，注意蛋糕块的长度必须为整数。
输入格式
第一行一个正整数 n（1≤ n ≤ 103），表示长条蛋糕的总长度。
第二行 n 个正整数 p1 ,p2 ,...,pn（ 1≤ pi ≤105），表示不同长度蛋糕块的价格。
输出格式
一行一个正整数，表示最大总销售价格。
输入样例 1
4
1 5 8 9输出样例 1
10输入样例 2
10
1 5 8 9 10 17 17 20 24 30输出样例 2
30参考答案
# 蛋糕长度
n = int(input())
# 蛋糕长度及其对应的价钱
p = list(map(int, input().split()))
p = [0] + p
# f[i][j] = 只使用长度 1..i 的蛋糕块，总长度为 j 时的最大总价
f = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if j >= i:
f[i][j] = max(f[i - 1][j], f[i][j - i] + p[i])
else:
f[i][j] = f[i - 1][j]
print(f[n][n])答案解析
# 蛋糕长度
n = int(input())
# 蛋糕长度及其对应的价钱
p = list(map(int, input().split()))
p = [0] + p
# f[j] 总长度 j 的最大总价
f = [0] * (n + 1)
# 当前可用最大蛋糕长度
for i in range(1, n + 1):
# 从小到大更新，允许重复选取同长度蛋糕
for j in range(i, n + 1):
f[j] = max(f[j], f[j - i] + p[i])
print(f[n])
上一题
下一题