首页 > 代码库 > hdu 3496 Watch The Movie
hdu 3496 Watch The Movie
题目:
链接:点击打开链接
题意:
想看n个电影,只能从中选m个,用l时间来看,这n个电影都要花费时间a[i]去看,也有一定的价值b[i],选取最大的价值。
思路:
这是二维费用背包,总时间l是背包容量,选m个是隐藏的花费,每个电影需要的时间a[i]也是花费。这样,状态转移方程就有了:dp[i][j] = max( dp[i][j] , dp[i-1][j-a[i]] + b[i] ),表示从n个电影中选i个电影花费j时间能够得到的总价值。
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define INF 0x7fffffff int dp[110][1010]; int a[110],b[110]; int n,m,l; int main() { //freopen("input.txt","r",stdin); int t; cin>>t; while(t--) { scanf("%d%d%d",&n,&m,&l); for(int i=0; i<=m; i++) { for(int j=0; j<=l; j++) dp[i][j] = -INF; } for(int i=0; i<=l; i++)//选0个电影时价值为0.。。 dp[0][i] = 0; for(int i=1; i<=n; i++) scanf("%d%d",&a[i],&b[i]); for(int i=1; i<=n; i++) { for(int j=m; j>=1; j--) { for(int k=l; k>=a[i]; k--) { dp[j][k] = max(dp[j][k],dp[j-1][k-a[i]]+b[i]); } } } if(dp[m][l] > 0) printf("%d\n",dp[m][l]); else printf("0\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。