終于通了第三章。
這個題目我設(shè)的三維狀態(tài)，dp[i][j][k]表示前i個歌曲放在前j個唱片中第j個唱片用了k分鐘的最大歌曲數(shù)。
轉(zhuǎn)移方程：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
跟背包問題差不多，就是加了一個唱片個數(shù)和容量的限制。三維狀態(tài)一維轉(zhuǎn)移，時間復(fù)雜度 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;
}