本文主要是介绍HDOJ 3732 Ahui Writes Word,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
杭电OJ 3732;l链接:http://acm.hdu.edu.cn/showproblem.php?pid=3732
Ahui Writes Word
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1977 Accepted Submission(s): 731
Question: the maximum value Ahui can get.
Note: input words will not be the same.
Each of the next N line are a string and two integer, representing the word, the value(Vi ) and the complexity(Ci ). (0 ≤ Vi , Ci ≤ 10)
5 20 go 5 8 think 3 7 big 7 4 read 2 6 write 3 5
15HintInput data is huge,please use “scanf(“%s”,s)”题目分析:首先,我们可以明确一点,输入数据中的字符串是没有作用的。然后,还有一点要注意,这道题目乍看上去像是01背包(注意数据量N≤ 100000,C ≤ 10000,直接套用01背包显然会超时),但是实际上是多重背包(0 ≤ Vi , Ci ≤ 10, (Vi,Ci)的组合最多就是121个,但是N最大是100000,所以里面会出现很多重复的(Vi,Ci),也就是多重背包了)。#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define max(x,y) x>y?x:yint dp[10010], num[12][12], weight[100010], value[100010];int main() {int n, c;while(~scanf("%d%d", &n, &c)){int valuea, price, count = 0;char s[20];memset(dp, 0, sizeof(dp));memset(num, 0, sizeof(num));memset(weight, 0, sizeof(weight));memset(value, 0, sizeof(value));for(int i = 1; i <= n; i++){scanf("%s%d%d", s, &valuea, &price);num[valuea][price]++;}for(int i = 0; i <= 10; i++){for(int k = 0; k <= 10; k++){int tmp = num[i][k];for(int j = 1; j <= tmp; j = j*2) // 二进制拆分 { weight[count] = j * k; value[count++] = j * i; tmp -= j; }if(tmp > 0) { weight[count] = tmp * k; value[count++] = tmp * i; } }}for(int i = 0; i < count; i++){for(int j = c; j >= weight[i]; j--){dp[j] = max(dp[j], dp[j-weight[i]]+value[i]);} }printf("%d\n", dp[c]);}return 0; }
这篇关于HDOJ 3732 Ahui Writes Word的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!