今天听了 doggu神 讲了这道题的另一种做法，真是脑洞大开、眼界大开。虽然复杂度比黄学长的要大一点，但不总结一下简直对不起这神思路。
Description
ftiasch 有 N 个物品, 体积分别是 W1, W2, …, WN。 由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N - 1 物品装满容积为 x 的背包，有几种方法呢？” – 这是经典的问题了。她把答案记为 Count(i, x) ，想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。 Input 第1行：两个整数 N (1 ≤ N ≤ 2 × 103) 和 M (1 ≤ M ≤ 2 × 103)，物品的数量和最大的容积。 第2行： N 个整数 W1, W2, …, WN, 物品的体积。 Output 一个 N × M 的矩阵， Count(i, x)的末位数字。 Sample Input 3 2 1 1 2 Sample Output 11 11 21 HINT 如果物品3丢失的话，只有一种方法装满容量是2的背包，即选择物品1和物品2。
这道题最开始会有两种想法：1、用总方案数减去用该物品的方案数，这个的分支的最终思路就是黄学长的做法。 2、去掉每一个物品，重新跑背包（这不是暴力吗喂？！）
假设我们没有想到 方法1，那该怎么办呢？我们可以很直观的感觉到：去掉i，我们要用1~i-1和i+1~n个物品去更新背包；去掉j，我们要用1~j-1和j+1~n个物品去更新背包。
其中大部分都是一样的，我们会直观的感觉到这是冗余部分，是不需要这么多次的，希望可以减少无用功。首先，背包有个性质：物品更新的先后顺序并不影响最终结果，这是肯定的。
我们想：如果去掉 i、j，用剩余的n-2个物品去更新。再用 j 更新，就得到了去掉 i 的答案；同理，再用 i 去更新，就得到了 j 答案。对于多个物品的块，亦然。
那么我们是否就想到了分治？把物品分为上述的块，再来解决？
那么对于当前的分治状态solve(int le,int ri)，此时我们已经用1~le-1和ri+1~n的物品将背包处理好了，直接处理该块没有意义，因为我们还可以将块分下去。将[le,ri]分为两段，如果要处理[le,mid]，就用mid+1~ri的物品将之前更新好了的背包再更新一遍；同理，处理[mid+1,ri]，就用le~mid的物品去更新之前的背包。 就这样递归下去，直到le==ri，这时的背包就是对于去掉le的答案了，输出即可。因为是这是中序遍历，一共有log层，所以只需开log个背包即可
复杂度：因为每一层都要跑背包，共log层，所以总时间复杂度o(nmlogn)，空间复杂度o(mlogn)
代码：
#include#include #include using namespace std;const int N=2000+5;int n,m,w[N];int f[15][N];void solve(int dep,int le,int ri){ if(le==ri){ for(int i=1;i<=m;i++) printf("%d",f[dep][i]%10); printf("\n"); return; } int mid=(le+ri)>>1; for(int j=0;j<=m;j++) f[dep+1][j]=f[dep][j]; for(int i=mid+1;i<=ri;i++) for(int j=m;j>=w[i];j--) f[dep+1][j]+=f[dep+1][j-w[i]],f[dep+1][j]%=10;//some items have been done solve(dep+1,le,mid); for(int j=0;j<=m;j++) f[dep+1][j]=f[dep][j]; for(int i=le;i<=mid;i++) for(int j=m;j>=w[i];j--) f[dep+1][j]+=f[dep+1][j-w[i]],f[dep+1][j]%=10; solve(dep+1,mid+1,ri);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&w[i]); f[0][0]=1; solve(0,1,n); return 0;}
就算不是最优的，但这思路实在是巧。提高自己的眼界总归是一件好事。