目录

可逆背包

问题简介

考虑这样一个问题：有 $n$ 个物品，体积分别是 $w_1,w_2,\cdots,w_n$，背包容量为 $m$，共有 $n$ 次询问，第 $i$ 次询问要求不选物品 $i$ 时共有多少选法装满背包。

思路分析

如果对于每个询问依次求 01 背包问题，单次询问需要 $O(nm)$ 的时间，总复杂度 $O(n^2m)$。而退背包能让我们不需要对于每个询问都进行完整的 DP，而是用 $O(m)$ 时间去掉选择了物品 $i$ 的方案数，那么整个过程需要一次 $O(nm)$ 的DP和 $n$ 次 $O(m)$ 的退背包/加背包过程，整体复杂度就降到了 $O(nm)$。

算法步骤

1. 执行一次 01 背包算法过程 

for(int j=m;j>=w[i];--j)
    f[j]+=f[j-w[i]];

2. 对每个物品，将其看作是最后一个加入背包的物品，然后减掉它的方案数 

memcpy(g,f,sizeof f);
for(int j=w[i];j<=m;++j)
    g[j]-=g[j-w[i]];

例题

例 1

洛谷 P4141 消失之物

题意

有 $n$ 个物品，体积分别是 $w_1,w_2,\cdots,w_n$，现第 $i$ 个物品丢失，用剩下的 $n-1$ 个物品装满容积为 $x$ 的背包，有几种方法。把答案记为 $cnt(i,x)$，要得到所有 $i\in[1,n],x\in[1,m]$ 的 $cnt(i,x)$ 表格。输出 $n\times m$ 的矩阵，表示 $cnt(i,x)$ 的末位数字。

$1\le n,m\le 2000$。

题解

令 $f[j][0]$ 表示不算消失的物品组成容积为 $j$ 的方案数，即 01 背包问题，令 $f[j][1]$ 表示删掉某个物品后组成容积为 $j$ 的方案数。初始化是 $f[0][0]=f[0][1]=1$，即容积为 0 时方案数为 1

查看代码

查看代码 

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int f[N][2],w[N];
 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    f[0][0]=f[0][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            f[j][0]=(f[j][0]+f[j-w[i]][0])%10;
        }
    }
 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j-w[i]>=0) f[j][1]=(f[j][0]-f[j-w[i]][1]+10)%10;
            else f[j][1]=f[j][0]%10;
            printf("%d",f[j][1]);
        }
        puts("");
    }
    return 0;
}

例 2

CF 1111 D. Destroy the Colony

题意

给定一个长度为偶数的由大小写字母组成的字符串 $s$，一个“好”字符串可通过重排字母顺序使得所有相同字母的位置都在 $s$ 的同一半（$[1,n/2] or [n/2+1,n]$）来生成。$q$ 个询问，给定一对 $(i,j)$，要求字母 $s[i],s[j]$ 也在 $s$ 的同一半的“好”字符串数量。

题解

注意到询问本质上最多只有 $52^2$ 种可能，则考虑先把所有询问算出来，最后 $O(1)$ 回答询问。

  1. 令 $k$ 为字母种数，统计各字母的出现次数 $c_1,c_2,\cdots,c_k$，若有 $i_1,i_2,\cdots,i_p$ 使得 $c_{i_1}+c_{i_2}+\cdots+c_{i_p}=\dfrac{n}{2}$，则把它们放到第一组，剩下的放到第二组，第一组的排列数为 $\dfrac{(\dfrac{n}{2})!}{c_{i_1}!c_{i_2}!\cdots c_{i_p}!}$，第二组排列数为 $\dfrac{(\dfrac{n}{2})!}{c_{j_1}!c_{j_2}!\cdots c_{j_s}!}$，总方法数为 $W=\dfrac{(\dfrac{n}{2})!(\dfrac{n}{2})!}{c_1!c_2!\cdots c_k!}$；
  2. 注意到 $c_i$ 求和为 $\dfrac{n}{2}$ 的组合数可用 01 背包来求，在没有 $(i,j)$ 限制下的“好”字符串数量为 $W*dp[n/2]*2$；
  3. 现考虑 $(i,j)$ 的限制，即字母 $s[i]$ 和 $s[j]$ 需在同一组中，等价于去掉字母 $s[i]$ 和 $s[j]$ 的 01 背包问题，即作了一次 01 背包问题后，再枚举 $i,j$ 做退背包过程，将去掉 $(i,j)$ 的 DP 值记作 $ans[i][j]$；
  4. 最后对每个询问直接 $O(1)$ 输出答案即可。

查看代码

查看代码 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+7;
typedef long long ll;
ll fastpow(ll x,ll y){
	ll ret=1;
	for(;y;x=x*x%mod,y>>=1)
		if(y&1) ret=ret*x%mod;
	return ret;
}
int conv(int x){
	if(x>='a') return x-'a'+26;
	return x-'A';
}
ll dp[N],fac[N],inv[N],temp_dp[N];
ll ans[55][55];
ll w[55];
int main(){
	string s;
	cin>>s;
	int n=s.length();
	fac[0]=1;
	w[conv(s[0])]++;
	for(int i=1;i<n;i++){
		w[conv(s[i])]++;
		fac[i]=fac[i-1]*i%mod;
	}
	fac[n]=fac[n-1]*n%mod;
	inv[n]=fastpow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	ll W=fac[n/2]*fac[n/2]%mod;
	for(int i=0;i<52;i++){
		if(w[i]) W=W*inv[w[i]]%mod;
	}
	dp[0]=1;
	for(int i=0;i<52;i++){
		if(w[i]){
			for(int j=n;j>=w[i];j--){
				dp[j]=(dp[j]+dp[j-w[i]])%mod;
			}
		}
	}
	for(int i=0;i<52;i++) ans[i][i]=dp[n/2];
	for(int i=0;i<52;i++){
		if(!w[i]) continue;
		for(int k=0;k<=n;k++) temp_dp[k]=dp[k];
 
		for(int k=w[i];k<=n;k++) temp_dp[k]=(temp_dp[k]-temp_dp[k-w[i]]+mod)%mod;
		for(int j=i+1;j<52;j++){
			if(!w[j]) continue;
			for(int k=w[j];k<=n;k++) temp_dp[k]=(temp_dp[k]-temp_dp[k-w[j]]+mod)%mod;
			ans[i][j]=2ll*temp_dp[n/2]%mod;
			ans[j][i]=ans[i][j];
			for(int k=n;k>=w[j];k--) temp_dp[k]=(temp_dp[k]+temp_dp[k-w[j]])%mod;
		}
	}
	int q;
	scanf("%d",&q);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		int l=conv(s[x-1]);
		int r=conv(s[y-1]);
		printf("%lld\n",W*ans[l][r]%mod);
	}
	return 0;
}