题目链接：uva 473 - Raucous Rockers
题目大意：有n首歌，以及m个磁带，每个磁带的容量为t，给出n首歌的大小，现在要将n首歌存放在m个磁带上，一首歌不能分开放，求最大的存放歌曲数。
解题思路：dp[i][j][k]表示第i首歌放在j磁盘的k位置（结束位置）时可以存放的最多歌曲数。
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][t]+1, dp[i-1][j-1][k-si]+1);
然后用滚动数组的话可以减少一维，因为如果不放的话，dp[i][j][k] = dp[i-1][j][k]。
#include#include #include using namespace std; const int N = 105; int n, m, t, k, dp[N][N]; int solve () { memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) { scanf("%d%*c", &k); for (int j = m; j >= 1; j--) { for (int x = t; x >= k; x--) { dp[j][x] = max(dp[j][x], dp[j-1][t]+1); dp[j][x] = max(dp[j][x], dp[j][x-k]+1); } } } return dp[m][t]; } int main () { int cas; scanf("%d", &cas); while (cas--) { scanf("%d%d%d", &n, &t, &m); printf("%d\n", solve()); if (cas) printf("\n"); } return 0; }