首页 > 代码库 > uva 473(dp)
uva 473(dp)
题意:按创作时间给出n首歌每首歌的时间ti,然后按创作时间装到m个光盘内,给出光盘最大分钟数t,问m个光盘最多总共放多少首歌。
题解:对于每首歌都能够选或者不选,假设选择了这首歌,是否把这首歌当做第j张光盘的第一首歌。
f[i][j][k]表示前i首歌放到第j张光盘里用分钟数是k的容量最多放多少首歌。
f[i][j][k] = f[i - 1][j][k]表示要选这首歌
f[i][j][k] = max(f[i][j][k], f[i][j - 1][t] + 1)表示把这首歌当做第j张光盘的第一首歌
f[i][j][k] = max(f[i][j][k], f[i][j][k-a[i]] + 1)表示不选这首歌当第j张光盘第一首歌
假设用二维滚动数组取代第一维,j要逆序枚举。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1000;
int n, m, t, f[N][N], a[N];
int main() {
int cas;
scanf("%d", &cas);
while (cas--) {
memset(f, 0, sizeof(f));
scanf("%d%d%d", &n, &t, &m);
for (int i = 1; i <= n; i++)
scanf("%d%*c", &a[i]);
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
for (int k = t; k >= a[i]; k--) {
f[j][k] = max(f[j][k], f[j - 1][t] + 1);
f[j][k] = max(f[j][k], f[j][k - a[i]] + 1);
}
}
}
printf("%d\n", f[m][t]);
if (cas)
printf("\n");
}
return 0;
}
uva 473(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。