Luogu P4141 消失之物背包分治

雨点打透心脏的1/2处 2021-11-17 15:30 201阅读 0赞

题意：给出$n$个物品的体积和最大背包容量$m$，求去掉一个物品$i$后，装满体积为$w\\in \[1,m\]$背包的方案数。

> 有 N 个物品, 体积分别是 W1, W2, …, WN。 由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N – 1 物品装满容积为 x 的背包，有几种方法呢？” — 这是经典的问题了。她把答案记为 Count(i, x) ，想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。
> 
> 输入：第1行：两个整数 N (1 ≤ N ≤ 2 × 10^3) 和 M (1 ≤ M ≤ 2 × 10^3)，物品的数量和最大的容积。
> 
> 　　　第2行： N 个整数 W1, W2, …, WN, 物品的体积。
> 
> 输出：一个 N × M 的矩阵， Count(i, x)的末位数字。

--------------------

思路：背包，分治。

提交次数：1次（课上刚讲的）

题解：

定义$solve(s,l,r)$表示第$s$层，所处区间$\[l,r\]$。

递归过程：拷贝上一层状态到本层，先将$\[md+1,r\]$的物品添加到背包中，然后$solve(s+1,l,md)$，然后清空本层状态，重置为上一层状态，再将$\[l,md\]$的物品添加到背包中，然后$solve(s+1,md+1,r)$，边界是$l==r$，此时只有$l$这个物品没有被添加进背包，所以输出就好了。

代码：

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cstring>
    #define R register int
    using namespace std;
    //你弱，有什么资格休息
    #define ull unsigned long long
    #define ll long long
    #define pause (for(R i=1;i<=10000000000;++i))
    #define In freopen("NOIPAK++.in","r",stdin)
    #define Out freopen("out.out","w",stdout)
    namespace Fread {
        static char B[1<<15],*S=B,*D=B;
    #ifndef JACK
        #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
    #endif
        inline int g() {
            R ret=0,fix=1; register char ch;
            while(!isdigit(ch=getchar()))
                fix=ch=='-'?-1:fix;
            if(ch==EOF) return EOF;
            do
                ret=ret*10+(ch^48);
            while(isdigit(ch=getchar()));
            return ret*fix;
        }
        inline bool isempty(const char& ch) {
            return (ch<=36||ch>=127);
        }
        inline void gs(char* s) {
            register char ch; while(isempty(ch=getchar()));
            do *s++=ch; while(!isempty(ch=getchar()));
        }
    }
    using Fread::g;
    using Fread::gs;
    
    namespace Luitaryi {
    const int N=2010;
    int n,m;
    int f[15][N],w[N];
    inline void solve(int s,int l,int r) {
        if(l==r) {
            for(R i=1;i<=m;++i) printf("%d",f[s-1][i]);
            putchar('\n'); return ;
        }
        R md=l+r>>1;
        memcpy(f[s],f[s-1],sizeof(f[s-1]));
        for(R i=md+1;i<=r;++i) for(R j=m;j>=w[i];--j) 
            f[s][j]+=f[s][j-w[i]],f[s][j]%=10;
        solve(s+1,l,md);
        memcpy(f[s],f[s-1],sizeof(f[s-1]));
        for(R i=l;i<=md;++i) for(R j=m;j>=w[i];--j)    
            f[s][j]+=f[s][j-w[i]],f[s][j]%=10;
        solve(s+1,md+1,r);
    }
    inline void main() {
        n=g(),m=g();
        for(R i=1;i<=n;++i) w[i]=g();
        f[0][0]=1; solve(1,1,n);
    }
    }
    
    signed main() {
        Luitaryi::main();
        return 0;
    }

--------------------

2019.07.14

转载于:https://www.cnblogs.com/Jackpei/p/11183857.html