首页 > 代码库 > HDU 2082 找单词 （多重背包）
HDU 2082 找单词 （多重背包）
题意:假设有x1个字母A， x2个字母B,..... x26个字母Z，同时假设字母A的价值为1，字母B的价值为2,..... 字母Z的价值为26。那么，对于给定的字母，可以找到多少价值<=50的单词呢？单词的价值就是组成一个单词的所有字母的价值之和，比如，单词ACM的价值是1+3+14=18，单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关，比如ACM与CMA认为是同一个单词）。
题解：把26个字母看做26种背包，有个数有价值，求价值不超过50的所有可能个数，就是标准的多重背包。
但是这儿我们处理时要注意：首先是枚举1到26种背包，接着要枚举价值1到50，再枚举每种背包个数
原因是：我们需要处理的是：对每种价值要用背包来求出可能个数
还有就是这儿我们求个数时，只需要把0赋值为1，其他要赋值成0
#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<vector>#include<string>#include<cstdio>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0#define mul(a,b) (a<<b)#define dir(a,b) (a>>b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const ll INF=1ll<<60;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=100;ll dp[Max],val[Max];ll Pack(int n){ for(int i=1; i<51; ++i) dp[i]=0ll; dp[0]=1ll; for(int i=1; i<=n; ++i) { for(int j=50; j>0; --j) { for(int k=1; k<=val[i]; ++k) { if(j-k*i>=0) dp[j]+=dp[j-k*i]; } } } ll sum=0ll; for(int i=1; i<51; ++i) sum+=max(dp[i],0ll); return sum;}int main(){ std::ios::sync_with_stdio(false); int t; cin >> t; while(t--) { for(int i=1; i<=26; ++i) cin >> val[i]; cout << Pack(26) << endl; } return 0;}
HDU 2082 找单词 （多重背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。