hdu 1709 求天平不能称重的重量动态规划

﹏ヽ暗。殇╰゛Y 2022-08-03 15:57 103阅读 0赞

给定一个天平和n个砝码，每个砝码都有一个重量，求出从1到这些砝码的总和之间不能被天平表示的重量。天平可以两端放砝码。

动态规划做法，看网上都是母函数，真心不懂。。

dp\[i\]如果是0表示这些砝码不能称重i重量，如果是1表示能称重i重量。

对于每个砝码，假设当前砝码重量是b\[i\]，那么j从最大值开始，减小到b\[i\]，

如果存在一个dp\[j-b\[i\]\]为1，说明当前的j能被组成。

j逆着循环的原因是由于每个砝码只有 一个，类似于01背包与完全背包的样子，

如果正向循环会导致每个物品可能使用多次，逆向循环则不会出现这个问题。

其实举个例子就能看出来了。

因为天平是可以两边放的，因此可以从大的数中减去小的数，方法就是对于每个砝码重量b\[i\]，

遍历在dp数组中为真的并且比b\[i\]那些j，那么dp\[j-b\[i\]\]也一定为真，这个乍一看不靠谱，但经过分析好像是对的。

如果b\[i\]被重复使用了怎么办？即dp\[j\]已经使用了b\[i\]了，你还要减去b\[i\]，但它只有一个啊。

此时如果dp\[j\]已经使用了b\[i\]，那么dp\[j-b\[i\]\]早已经为真了，即由别的砝码早可以组成dp\[j-b\[i\]\]了。

如果是多个砝码减2个砝码怎么办？不会漏掉吗？其实在第一个砝码的时候就记录了多个砝码减第一个砝码的结果，

到第二个砝码的时候会用到这个结果。这样就不会漏了。

其实这也是dp，这个dp的j要正向进行，逆向进行就会导致砝码重复使用。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    const int N=100006;
    int dp[N];    //注意要大一些, 因为范围是砝码的总和
    int b[2006];
    
    int ans[20000];
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            mem(dp,0);
            int mx=0;
            for(int i=0;i<n;i++)
            {
                b[i]=in();
                mx+=b[i];
            }
    
            dp[0]=1;
            for(int i=0;i<n;i++)
            {
                for(int j=mx;j>=b[i];j--)
                {
                    if(dp[j-b[i]]) dp[j]=1;
                }
            }
            for(int i=0;i<n;i++)
            {
                for(int j=b[i];j<=mx;j++)
                {
                    if(dp[j])dp[j-b[i]]=1;  //每个比当前砝码大的，减去当前砝码的重量。
                }
            }
            int p=0;
            for(int i=1;i<=mx;i++)if(!dp[i])ans[p++]=i;
            printf("%d\n",p);
            for(int i=0;i<p-1;i++)
            {
                printf("%d ",ans[i]);
            }
            if(p>0)printf("%d\n",ans[p-1]);  //当时又漏了p>0
    
    
        }
        return 0;
    }