P4141 消失之物 题解

· · 题解

题意

给你 n 个物品的重量 w_1,w_2,\dots,wn 求排除第 i 个书包后求重量和为 x\in [1,m] 的方案数。

思路

不知道为什么没有人用分治（
对于一段区间 (l,r)，分别将 (l,mid) 与 (mid+1,r) 做背包，再处理剩余的区间。当 l=r 时，就可以直接给出答案了！
因为每一次我们都对没做背包的部分的一半又做了背包，又因为背包答案与顺序无关，所以 l=r 时，就只有 l 没有算入背包了，正好就是答案！
时间复杂度是分治加背包,O(nm log (n))。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

namespace acac
{
    int dp[2010][2010];
    int Ans[2010][2010];
    int W[2010];
    int n,m;
    const int mod=10;
    void sovle(int dep,int l,int r)//分治,dep是为了方便处理现在(l,r)的背包 
    {
        if(l==r)//背包正好有一个没处理 
        {
            for(int i=1;i<=m;i++) 
            {
                Ans[l][i]=dp[dep-1][i];
            }
            return ;
        }
        int mid=(l+r)>>1;
        for(int i=0;i<=m;i++)
        {
            dp[dep][i]=dp[dep-1][i];
        }
        for(int i=l;i<=mid;i++)//处理左半边 
        {

            for(int j=m;j>=W[i];j--)
            {
            //  if(dep==1)cout<<j-W[i]<<' '<<dp[dep][j-W[i]]<<endl;
                dp[dep][j]=(dp[dep][j]+dp[dep][j-W[i]])%mod;
            }
        }
        sovle(dep+1,mid+1,r);//去还未处理的右半边 
        for(int i=0;i<=m;i++)//重置，不然左边会算进来 
        {
            dp[dep][i]=dp[dep-1][i];
        }
        for(int i=mid+1;i<=r;i++)//处理右半边 
        {
            for(int j=m;j>=W[i];j--)
            {
                dp[dep][j]=(dp[dep][j]+dp[dep][j-W[i]])%mod;
            }
        }
        sovle(dep+1,l,mid);//去还未处理的左半边 

    } 

    int main()
    {
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&W[i]);
        }
        dp[0][0]=1;
        sovle(1,1,n);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cout<<Ans[i][j];
            }
            cout<<'\n';
        }
        return 0;
    }
}
#undef int
int main()
{
    acac::main();
    return 0;
}

其他

为什么这题可以暴力回退？是因为这题为方案数，总答案一定会算删去物品的贡献，但是如果像 01背包一样不一定算删去物品的贡献就会汗流浃背。而这种方法就很好规避了这种问题。 还可以避免减法取模 。
不妨试试！