录制唱片dfbbjydetf

Question

录制唱片
内存限制: 256 Mb时间限制: 1000 ms
题目描述
乐队有
N 部作品，编号为
1 到
N，其中第
i 首歌的长度为
T
i
分钟。小爱想从中精选一些歌曲，把歌录到唱片里，然后出版一套专辑。这套专辑最多可以有
K 张唱片
每张唱片里可以录多首歌，但它们的总长不能超过
C 分钟。每首歌必须完整地放在一张唱片里，一首歌不能分割成两段放在两张唱片里，此外，录制唱片的时候，还要注意保持歌曲的编号顺序。

假设小爱选录编号为
1,3,5 的歌曲，她不能把

1,5 放在第一张唱片里，而把
3 放在第二场唱片里，因为
3 的编号比
5 更小。
考虑到这些要求之后，请问小爱应该选择录制哪些歌曲，才能让出版的专辑收入尽量多的歌曲？

输入格式
第一行：三个整数
N，

C 和

第二行到第

N+1行：在第

i+1 行有一个整数

输出格式
单个整数：表示可以装进专辑的歌曲数目
数据范围
1000
1≤N≤1000
10000
1≤C≤10000
10000
1≤K≤10000
≤10000
c++

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

思路：动态规划 问题可以转化为，给定一个长度为N的数组songs，其中songs[i]表示第i首歌的长度，现在需要在songs中选择一些歌曲，使得它们的总长度不超过C，但是选择的歌曲编号必须是连续的，并且需要选择若干个这样的连续编号的歌曲，使得它们的总长度最大，求最大总长度。 定义状态dp[i]表示以第i首歌结尾的连续编号歌曲的最大总长度，对于dp[i]来说，它有两种情况，即选择第i首歌和不选择第i首歌。 如果选择第i首歌，那么它必须作为一个新的连续编号歌曲的结尾，此时，dp[i] = songs[i]。 如果不选择第i首歌，那么dp[i] = dp[i-1]。 综上，状态转移方程为： dp[i] = max(songs[i], dp[i-1]+songs[i]) 其中，songs[i]为选择第i首歌的情况，dp[i-1]+songs[i]为不选择第i首歌的情况，注意dp[i-1]+songs[i]表示的是以第i-1首歌结尾的连续编号歌曲，此时加上第i首歌，就可以构成以第i首歌结尾的连续编号歌曲。 最后，在dp数组中找到最大的值，即为最大总长度。 代码实现：