[AHOI2002]Kitty猫基因突变
WA鸭鸭
·
·
题解
以下设 n=2^k
首先分析 T 函数性质，我们可以将 T 函数抽象为在线段树上求解，每次如果整个区间全 0 或全 1 则 cnt++ 并返回（其实就是按照题意模拟）。那么 cnt 的值就是 T 序列内 A 与 B 的个数和。
按照套路，设 $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$ 是否合法。
我们可以发现只有线段树上的区间转移是合法的，我们仿照建树过程，将所有合法转移求出。
```cpp
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` 的个数，转移使用的是从前往后推，非上述）：
```cpp
#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;
}
```