- 貌似是某年提高组签到题，六重循环零压力AC，差点怒踩std
- 但本蒟蒻决定写正解——多重背包，果断20分
- 原因是写错了状态转移方程。。。神才知道我咋过的样例和两个测试点
- 扯远了
多重背包
- 简单说一下多重背包
- 限制某一些物体个数的背包
- 可以参考fengzw的背包问题：0-1背包、完全背包和多重背包
- 这里只说一下二进制拆分
- 我们要保证可以选出一个物品的所有可能数量
- 若它有n个，那么从20开始，一直到⌊log2n⌋中，每次以2k分为一组
- 剩下的n-⌊log2n⌋单独为一组即可
- 可以证明这种方法正确，在此不再赘述
- 然后就是一个愉快的01背包
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 bool dp[10005]; 6 7 int a,weight[7]={0,1,2,3,5,10,20},tot,v[10005],ans; 8 9 inline int read(void){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){ 12 if(ch=='-') f=-1; 13 ch=getchar(); 14 } 15 while(ch>='0'&&ch<='9'){ 16 x=(x<<1)+(x<<3)+ch-'0'; 17 ch=getchar(); 18 } 19 return x*f; 20 } 21 22 void cf(int x,int y){ 23 for(register int i=1;x-i>=0;i<<=1) 24 v[++tot]=weight[y]*i,x-=i; 25 if(x) v[++tot]=weight[y]*x; 26 } 27 28 int main(){ 29 for(register int i=1;i<=6;i++) 30 a=read(),cf(a,i); 31 dp[0]=1; 32 for(register int i=1;i<=tot;i++) 33 for(register int j=10000-v[i];j>=0;j--) 34 dp[j+v[i]]|=dp[j]; 35 for(register int i=1;i<=10000;i++) 36 if(dp[i]) ans++; 37 printf("Total=%dn",ans); 38 return 0; 39 }
毕竟是一个可行性背包大水题，愉快地A了！
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
