当前位置：首页 > news >正文

UVa 473 Raucous Rockers

news 2026/6/13 21:21:44

题目描述

题目要求将nnn首歌曲按创作时间顺序分配到mmm张光盘上，每张光盘容量为ttt分钟，每首歌曲不能拆分到多张光盘。目标是最大化被选中的歌曲数量。

输入格式

第一行一个整数DDD，表示数据集的个数，后面跟一个空行。每个数据集的第一行包含三个整数nnn、ttt、mmm。第二行包含nnn个整数，表示每首歌曲的长度（单位为分钟）。每个ti<tt_i < tti<t，且∑ti>m×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×t，nnn最大未知，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首歌曲：
- 若放入当前光盘（k+ti≤tk + t_i \le tk+ti≤t）：dp[i][j][k+ti]=max⁡(dp[i][j][k+ti],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][k+ti]=max(dp[i][j][k+ti],dp[i−1][j][k]+1)
- 若放入新光盘（j<mj < mj<m）：dp[i][j+1][ti]=max⁡(dp[i][j+1][ti],dp[i−1][j][k]+1)\textit{dp}[i][j+1][t_i] = \max(\textit{dp}[i][j+1][t_i], \textit{dp}[i-1][j][k] + 1)dp[i][j+1][ti]=max(dp[i][j+1][ti],dp[i−1][j][k]+1)

简化

由于nnn、mmm、ttt的具体范围未给出，但ti<tt_i < tti<t，且∑ti>m×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≤tdp[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//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intdatasets;cin>>datasets;for(intds=0;ds<datasets;++ds){if(ds)cout<<'\n';intn,t,m;cin>>n>>t>>m;vector<int>songs(n);charcomma;for(inti=0;i<n;++i){cin>>songs[i];if(i<n-1)cin>>comma;}// dp[j][k]: 使用 j 张光盘，当前光盘已用 k 分钟时，最多歌曲数vector<vector<int>>dp(m+1,vector<int>(t+1,-1));dp[0][0]=0;for(inti=0;i<n;++i){intlength=songs[i];// 逆序更新，避免重复使用当前歌曲for(intj=m;j>=0;--j){for(intk=t;k>=0;--k){if(dp[j][k]<0)continue;// 尝试放入当前光盘if(k+length<=t){dp[j][k+length]=max(dp[j][k+length],dp[j][k]+1);}// 尝试放入新光盘if(j<m){dp[j+1][length]=max(dp[j+1][length],dp[j][k]+1);}}}}intans=0;for(intj=0;j<=m;++j){for(intk=0;k<=t;++k){ans=max(ans,dp[j][k]);}}cout<<ans<<'\n';}return0;}