洛谷P2347 砝码称重

貌似是某年提高组签到题，六重循环零压力AC，差点怒踩std
但本蒟蒻决定写正解——多重背包，果断20分
原因是写错了状态转移方程。。。神才知道我咋过的样例和两个测试点
扯远了

多重背包

简单说一下多重背包
限制某一些物体个数的背包
可以参考fengzw的背包问题：0-1背包、完全背包和多重背包
这里只说一下二进制拆分
我们要保证可以选出一个物品的所有可能数量
若它有n个，那么从2⁰开始，一直到⌊log₂n⌋中，每次以2^k分为一组
剩下的n-⌊log₂n⌋单独为一组即可
可以证明这种方法正确，在此不再赘述
然后就是一个愉快的01背包

 #include<bits/stdc++.h>

 using namespace std;

 bool dp[];

 int a,weight[]={,,,,,,},tot,v[],ans; 

 inline int read(void){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){

         if(ch=='-') f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<=''){

         x=(x<<)+(x<<)+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 void cf(int x,int y){

     for(register int i=;x-i>=;i<<=)

         v[++tot]=weight[y]*i,x-=i;

     if(x) v[++tot]=weight[y]*x;

 }

 int main(){

     for(register int i=;i<=;i++)

         a=read(),cf(a,i);

     dp[]=;

     for(register int i=;i<=tot;i++)

         for(register int j=-v[i];j>=;j--)

             dp[j+v[i]]|=dp[j];

     for(register int i=;i<=;i++)

         if(dp[i]) ans++;

     printf("Total=%d\n",ans);

     return ;

 }

毕竟是一个可行性背包大水题，愉快地A了！

秒客网

洛谷P2347 砝码称重

相关文章