自动搬运

查看原文

来自洛谷，原作者为

	WA鸭鸭 暴风城的各位酱鸭萌，听我号令！

搬运于2025-08-24 21:39:04，当前版本为作者最后更新于2021-10-01 10:01:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

以下设 $n=2^k$

首先分析 $T$ 函数性质，我们可以将 $T$ 函数抽象为在线段树上求解，每次如果整个区间全 $0$ 或全 $1$ 则 cnt++ 并返回（其实就是按照题意模拟）。那么 cnt 的值就是 $T$ 序列内 $A$ 与 $B$ 的个数和。

$C$ 的个数为 $cnt-1$ ，这一点很好证明。所以 $T$ 的价值就可以通过 $cnt$ 直接确定，我们的目标就是让 $A(s,s')=2\times cnt-1+C(s,s')$ 最小。（ $C(s,s')$ 为修改代价）由于式子里的 -1 很麻烦，所以我们先求出 $A(s,s')+1$，输出时再将答案 -1 。

按照套路，设 $f_{i,j}$ 表示前 $i$ 个基因单元，修改了 $j$ 个 的 $A(s,s')$ 最小值。

记 sum1[] 为 前 $i$ 个基因单位全部修改为 $1$ 的代价和， sum2[] 为 前 $i$ 个基因单位里 $0$ 的个数。

选择一段区间，全部修改为 $1$ ：

$$f_{i,j}=\min_{\text{p转移到i合法}}f_{p,j-(sum2[i]-sum2[p])}+(sum1[i]-sum1[p])+2 $$

选择一段区间，全部修改为 $0$ ：

$$f_{i,j}=\min_{\text{p转移到i合法且区间[p+1,i]内全为0}}f_{p,j}+2 $$

最后的问题是如何求出 $p$ 转移到 $i$ 是否合法。

我们可以发现只有线段树上的区间转移是合法的，我们仿照建树过程，将所有合法转移求出。

void build(int l,int r)
{
	t[l-1].push_back(r);//t[x]表示x可以往后转移的点
	if(l==r)return;
	int mid=(l+r)>>1;
	build(l,mid);
	build(mid+1,r);
}

复杂度 $O(nw)$ ，可以轻松通过。

全部代码（请注意这里的 sum2[] 是 1 的个数，转移使用的是从前往后推，非上述）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int n,w;
int c[100001],sum1[100001],sum2[100001];
vector<int>t[100001];
int f[1001][31];
void build(int l,int r)
{
	t[l-1].push_back(r);
	if(l==r)return;
	int mid=(l+r)>>1;
	build(l,mid);
	build(mid+1,r);
}
int main()
{
	memset(f,0x3f,sizeof(f));
	cin>>n>>w;
	n=(1<<n);
	for(int i=1;i<=n;i++)
	{
		scanf("%1d",&c[i]);
	}
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		sum1[i]=sum1[i-1]+(!c[i])*x;
		sum2[i]=sum2[i-1]+c[i];
	} 
	build(1,n);
	f[0][0]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=w;j++)
		{
			for(int k=0;k<t[i].size();k++)
			{
				int r=t[i][k];
				if(sum2[r]==sum2[i])f[r][j]=min(f[r][j],f[i][j]+2);
				int s=r-i-(sum2[r]-sum2[i]);
				if(j+s<=w)f[r][j+s]=min(f[r][j+s],f[i][j]+(sum1[r]-sum1[i])+2);
			}
		}
	}
	cout<<f[n][w]-1;
	return 0;
}