HDOJ 3535-AreYouBusy AreYouBusy Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3450 Accepted Submission(s): 1342 Problem Description Happy New Term! As having become a junior, xiaoA recognizes that there is not much time for her to AC problems, because there are some other things for her to do, which makes her nearly mad. What’s more, her boss tells her that for some sets of duties, she must choose at least one job to do, but for some sets of things, she can only choose at most one to do, which is meaningless to the boss. And for others, she can do of her will. We just define the things that she can choose as “jobs”. A job takes time , and gives xiaoA some points of happiness (which means that she is always willing to do the jobs).So can you choose the best sets of them to give her the maximum points of happiness and also to be a good junior(which means that she should follow the boss’s advice)? Input There are several test cases, each test case begins with two integers n and T (0<=n,T<=100) , n sets of jobs for you to choose and T minutes for her to do them. Follows are n sets of description, each of which starts with two integers m and s (0<m<=100), there are m jobs in this set , and the set type is s, (0 stands for the sets that should choose at least 1 job to do, 1 for the sets that should choose at most 1 , and 2 for the one you can choose freely).then m pairs of integers ci,gi follows (0<=ci,gi<=100), means the ith job cost ci minutes to finish and gi points of happiness can be gained by finishing it. One job can be done only once. Output One line for each test case contains the maximum points of happiness we can choose from all jobs .if she can’t finish what her boss want, just output -1 . Sample Input 3 3 2 1 2 5 3 8 2 0 1 0 2 1 3 2 4 3 2 1 1 1 3 4 2 1 2 5 3 8 2 0 1 1 2 8 3 2 4 4 2 1 1 1 1 1 1 0 2 1 5 3 2 0 1 0 2 1 2 0 2 2 1 1 2 0 3 2 2 1 2 1 1 5 2 8 3 2 3 8 4 9 5 10 Sample Output 5 13 -1 -1 Author hphp Source 2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU Recommend zhouzeyong | We have carefully selected several similar problems for you: 3033 1712 3449 2639 2159
本题分三种集合，第0种集合内至少要取1个任务；第1种集合内至多取1一个任务；第2种集合内没有任何限制。 集合内部是背包问题，这3种集合之间也是一个背包问题。 假设dp[i][j]表示前i个集合中，耗时为j时取得的最大幸福数量，则： 在第0种集合中，因为至少要取1个任务（耗时c，幸福数g），这个任务可以是本集合的第一个任务dp[i-1][j-c]+g，因为是第一个任务，所以基准是上一个集合i-1；也可以不是第一个任务dp[i][j-c]+g，基准就是本集合i；可以不取这个任务dp[i][j]，所以dp[i][j]=max(dp[i][j], dp[i-1][j-c]+g, dp[i][j-c]+g)，为了至少取一个任务，dp[i][j]必须小于其他2个，所以令dp[i][j]的初始值为-INF。 在第1种集合中，至多取1个任务，都是基于上一个集合，所以不取dp[i-1][j]；取dp[i-1][j-c]+g。 在第2种集合中，是常规0/1背包问题，不取dp[i-1][j]；第一次取dp[i-1][j-c]+g；不是第一次取dp[i][j-c]+g。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; const int kMaxN = 105, kINF = 0x7ffffff; int dp[kMaxN][kMaxN]; int main() { //freopen("input.txt", "r", stdin); int n, t; while (~scanf("%d %d", &n, &t)) { for (int i = 0; i < kMaxN; i++) for (int j = 0; j < kMaxN; j++) dp[i][j] = -kINF; for (int i = 0; i < kMaxN; i++) dp[0][i] = 0; int m, s, c, g; for (int i = 1; i <= n; i++) { scanf("%d %d", &m, &s); if (s == 0) { while (m–) { scanf("%d %d", &c, &g); for (int j = t; j >=c; j–) dp[i][j] = max(dp[i][j], max(dp[i – 1][j – c] + g, dp[i][j – c] + g)); } } else if (s == 1) { for (int j = t; j >= 0; j–) dp[i][j] = dp[i – 1][j]; while (m–) { scanf("%d %d", &c, &g); for (int j = t; j >= c; j–) dp[i][j] = max(dp[i][j], dp[i – 1][j – c] + g); } } else if (s == 2) { for (int j = t; j >= 0; j–) dp[i][j] = dp[i – 1][j]; while (m–) { scanf("%d %d", &c, &g); for (int j = t; j >= c; j–) dp[i][j] = max(dp[i][j], max(dp[i – 1][j – c] + g, dp[i][j – c] + g)); } } } printf("%d\n", max(dp[n][t], -1)); } return 0; } [/cpp] 本代码提交AC，用时31MS，内存1616K。]]>