AtCoder Beginner Contest 269 G(DP)

题目链接
G - Reversible Cards 2（DP）

题意
有$N$张卡片，正面写有数字$A_i$，背面写有数字$B_i$，$\sum (A_i+B_i)=M$。对于$k\in [0,M]$，求最少翻转多少张卡片，使得所有卡片可见数字之和为$k$，不存在输出$-1$。

分析
用$f[i]$表示最少翻转$f[i]$次可以使得可见数字之和为$i$，根据状态表示有$f[S]=0$，$S=\sum A_i$.
考虑翻转一张卡片带来的影响，翻转第$i$张卡片可见数字之和增加$B_i-A_i$.接下来对问题进行抽象，将每张卡片看做一个物品，体积为$B_i-A_i$，花费为$1$，求最少选择多少个物品可以使花费最少，每个物品只能选一次，这样就转化为01背包问题，容易想到 $O(NM)$ 的做法。

const int N=2e5+10;
int a[N],b[N],f[N],g[N];
int n,m,sum;

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++) sum+=a[i],a[i]=b[i]-a[i];
	f[sum]=0;
	for(int i=1;i<=n;i++)
	{
		int x=a[i];
		for(int j=0;j<=m;j++) g[j]=f[j];
		for(int j=0;j<=m;j++)
		{
			if(x+j>=0&&x+j<=m)
			{
				g[x+j]=min(g[x+j],f[j]+1);
			}
		}
		for(int j=0;j<=m;j++) f[j]=g[j];
	}
	for(int i=0;i<=m;i++)
	{
		if(f[i]==0x3f3f3f3f) cout<<-1<<endl;
		else cout<<f[i]<<endl;
	}
	return 0;
}

$O(NM)$的复杂度不能通过本题，需要进行优化。由于$\sum |B_i-A_i|\le \sum (A_i+B_i)=M$，可知最多有 $\sqrt{M}$ 种不同的$|B_i-A_i|$，$B_i-A_i$ 最多有 $2\sqrt{M}$ 种取值。通过上面的分析，可以对具有相同体积的物品进行合并，这样问题从01背包转化为多重背包。多重背包可以通过二进制拆分进行优化，时间复杂度为$O(M\sqrt{M})$，可以通过本题。虽然对于单个物品来说，复杂度还有一个$log$，但通过均摊最终的复杂度不带$log$。可以从直观上理解，物品种类越多时，单个物品的个数就越少，$log$接近一个常数，当物品种类很少时，时间复杂度变为$Mlog(M)$，运行速度相对更快。

AC代码

const int N=2e5+10;
int a[N],b[N],f[N],cnt[N<<1];
int n,m,sum;

void solve(int x,int v)
{
	if(x>0)
	{
		for(int i=m-x;i>=0;i--)
		{
			f[i+x]=min(f[i+x],f[i]+v);
		}
	}
	else
	{
		for(int i=-x;i<=m;i++)
		{
			f[i+x]=min(f[i+x],f[i]+v);
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		cnt[b[i]-a[i]+m]++;
	}
	f[sum]=0;
	for(int i=-m;i<=m;i++)
	{
		if(cnt[i+m]&&i)
		{
			int c=cnt[i+m];
			int j=1;
			while(c>=j)
			{
				c-=j;
				solve(i*j,j);
				j<<=1;
			}
			if(c) solve(i*c,c);
		}
	}
	for(int i=0;i<=m;i++)
	{
		if(f[i]==0x3f3f3f3f) cout<<-1<<endl;
		else cout<<f[i]<<endl;
	}
	return 0;
}

注意
使用一维数组表示状态，要注意状态转移顺序，一个状态只能被同一个物品更新一次。