首页 > 代码库 > 【HDOJ】3496 Watch The Movie
【HDOJ】3496 Watch The Movie
二维费用背包。
1 #include <stdio.h> 2 #include <string.h> 3 4 #define mymax(a, b) (a>b) ? a:b 5 6 int dp[105][1005]; 7 int time[105], val[105]; 8 9 int main() { 10 int case_n; 11 int n, m, l; 12 int i, j, k; 13 14 scanf("%d", &case_n); 15 16 while (case_n--) { 17 scanf("%d%d%d", &n, &m, &l); 18 for (i=1; i<=n; ++i) 19 scanf("%d %d", &time[i], &val[i]); 20 memset(dp, 0xff, sizeof(dp)); 21 dp[0][0] = 0; 22 for (i=1; i<=n; ++i) { 23 for (k=m; k>0; --k) { 24 for (j=l; j>=time[i]; --j) { 25 if (dp[k-1][j-time[i]] != -1) { 26 dp[k][j] = mymax(dp[k][j], dp[k-1][j-time[i]]+val[i]); 27 } 28 } 29 } 30 } 31 k = 0; 32 for (i=0; i<=l; ++i) { 33 if (dp[m][i] > k) 34 k = dp[m][i]; 35 } 36 printf("%d\n", k); 37 } 38 39 return 0; 40 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。