题目描述题目要求将nnn首歌曲按创作时间顺序分配到mmm张光盘上每张光盘容量为ttt分钟每首歌曲不能拆分到多张光盘。目标是最大化被选中的歌曲数量。输入格式第一行一个整数DDD表示数据集的个数后面跟一个空行。每个数据集的第一行包含三个整数nnn、ttt、mmm。第二行包含nnn个整数表示每首歌曲的长度单位为分钟。每个titt_i tti​t且∑tim×t\sum t_i m \times t∑ti​m×t。两个连续数据集之间由一个空行分隔。输出格式对于每个数据集输出一行一个整数表示能放入mmm张光盘的最大歌曲数量。两个连续数据集的输出之间由一个空行分隔。样例输入2 10 5 3 3,5,1,2,3,5,4,1,1,5 1 1 1 1输出6 1题目分析本题的核心是在保持歌曲原有顺序的前提下将它们分配到mmm个容量为ttt的背包中使得放入的歌曲数量最多。这是一个多维背包问题可以用动态规划求解。动态规划定义设dp[i][j][k]\textit{dp}[i][j][k]dp[i][j][k]表示考虑前iii首歌曲使用了jjj张光盘且当前光盘已用容量为kkk时能够放入的最大歌曲数量。但这样状态数为n×m×tn \times m \times tn×m×tnnn最大未知t≤?t \le ?t≤?可接受。状态转移不选第iii首歌曲dp[i][j][k]max⁡(dp[i][j][k],dp[i−1][j][k])\textit{dp}[i][j][k] \max(\textit{dp}[i][j][k], \textit{dp}[i-1][j][k])dp[i][j][k]max(dp[i][j][k],dp[i−1][j][k])选第iii首歌曲若放入当前光盘kti≤tk t_i \le tkti​≤tdp[i][j][kti]max⁡(dp[i][j][kti],dp[i−1][j][k]1)\textit{dp}[i][j][k t_i] \max(\textit{dp}[i][j][k t_i], \textit{dp}[i-1][j][k] 1)dp[i][j][kti​]max(dp[i][j][kti​],dp[i−1][j][k]1)若放入新光盘jmj mjmdp[i][j1][ti]max⁡(dp[i][j1][ti],dp[i−1][j][k]1)\textit{dp}[i][j1][t_i] \max(\textit{dp}[i][j1][t_i], \textit{dp}[i-1][j][k] 1)dp[i][j1][ti​]max(dp[i][j1][ti​],dp[i−1][j][k]1)简化由于nnn、mmm、ttt的具体范围未给出但titt_i tti​t且∑tim×t\sum t_i m \times t∑ti​m×t可以假设ttt不大。实际上可以使用一维DP\texttt{DP}DP优化空间。算法初始化dp[0][0]0\textit{dp}[0][0] 0dp[0][0]0其他为−∞-\infty−∞。遍历每首歌曲iii从后向前更新避免同一首歌被多次使用对于每张光盘jjj从m−1m-1m−1到000对于每个容量kkk从t−tit - t_it−ti​到000更新放入当前光盘的状态。对于每张光盘jjj从m−1m-1m−1到000对于每个容量kkk更新放入新光盘的状态。最终答案为max⁡0≤j≤m,0≤k≤tdp[j][k]\max_{0 \le j \le m, 0 \le k \le t} \textit{dp}[j][k]max0≤j≤m,0≤k≤t​dp[j][k]。复杂度分析时间复杂度O(n×m×t)O(n \times m \times t)O(n×m×t)空间复杂度O(m×t)O(m \times t)O(m×t)。对于合理范围内的nnn、mmm、ttt可接受。代码实现// Raucous Rockers// UVa ID: 473// Verdict: Accepted// Submission Date: 2025-12-03// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intdatasets;cindatasets;for(intds0;dsdatasets;ds){if(ds)cout\n;intn,t,m;cinntm;vectorintsongs(n);charcomma;for(inti0;in;i){cinsongs[i];if(in-1)cincomma;}// dp[j][k]: 使用 j 张光盘当前光盘已用 k 分钟时最多歌曲数vectorvectorintdp(m1,vectorint(t1,-1));dp[0][0]0;for(inti0;in;i){intlengthsongs[i];// 逆序更新避免重复使用当前歌曲for(intjm;j0;--j){for(intkt;k0;--k){if(dp[j][k]0)continue;// 尝试放入当前光盘if(klengtht){dp[j][klength]max(dp[j][klength],dp[j][k]1);}// 尝试放入新光盘if(jm){dp[j1][length]max(dp[j1][length],dp[j][k]1);}}}}intans0;for(intj0;jm;j){for(intk0;kt;k){ansmax(ans,dp[j][k]);}}coutans\n;}return0;}