终于通了第三章。
这个题目我设的三维状态，dp[i][j][k]表示前i个歌曲放在前j个唱片中第j个唱片用了k分钟的最大歌曲数。
转移方程：dp[i][j][k] = max{ dp[i-1][j][k-w[i]] + 1, dp[i-1][j][k], dp[i-1][j-1][p] } p = 0...t
跟背包问题差不多，就是加了一个唱片个数和容量的限制。三维状态一维转移，时间复杂度 O(n * m * t * t)
/*
ID: shyprom1
PROG: rockers
LANG: C++
*/
#include <cstdio>
int main()
{
freopen("rockers.in", "r", stdin);
freopen("rockers.out", "w", stdout);
const int N = 32;
int n, m, t, v, dp[N][N] = {0}, ans = 0;
scanf("%d %d %d", &n, &t, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &v);
for (int j = 1; j <= m; j++)
{
for (int k = t; k >= 0; k--)
{
for (int p = 1; p <= t; p++)
dp[j][k] >?= dp[j-1][p];
if (k >= v)
dp[j][k] >?= dp[j][k-v] + 1;
}
}
}
for (int i = 0; i <= t; i++)
ans >?= dp[m][i];
printf("%d\n", ans);
return 0;
}