本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-23 22:48:32

题意

给出一个只包含 $0$ 和 $1$ 的字符串，每个字符取反需要一定代价，要求最后使串中有且仅有一组相邻字符相同，求最小代价。

思路

考虑动态规划（或者说是递推）。

首先能想到的是设 $f_i$ 表示前 $i$ 个字符的答案。

然而我们发现难以从 $f_{i-1}$ 向 $f_{i}$ 转移，有以下两个问题需要解决：

• 转移时当前位是否要改变？这还与上一位的值有关。
• 相同的那组字符在哪？是这一位与上一位还是在这一位之前？

为了解决这两个问题，我们就要增加状态的维度，于是有了新的状态：设 $f_{i,j,k}$ 为前 $i$ 位中有 $j$ 组相同的相邻字符，且第 $i$ 位为 $k$ 的最小代价。显然这里的 $j,k$ 都只有 $0$ 和 $1$ 两种取值。

接下来考虑转移：$f_{i,0}$ 只能从 $f_{i-1,0}$ 转移来，分为修改和不修改两种。而 $f_{i,1}$ 可从 $f_{i-1,0}$ 且令第 $i$ 位与上一位相同，或 $f_{i-1,1}$ 且令第 $i$ 位与上一位不同转移来。

最后是边界：显然有 $f_{1,0,a_i}=0,f_{1,0,!a_i}=c_i,f_{1,1,0}=f_{1,1,1}=+\infty$

答案即为 $f_{n,1,0}$ 与 $f_{n,1,1}$ 的较小值。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=2e5+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
char s[N];
int n,a[N],c[N],f[N][2][2];\/\/状态如上述 
signed main()
{
	n=read();
	cin>>s;
	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0',c[i]=read(); 
	f[1][0][a[1]]=0,f[1][0][!a[1]]=c[1];
	f[1][1][a[1]]=f[1][1][!a[1]]=1e18;\/\/初值 
	for(int i=2;i<=n;i++)
	{
		f[i][0][a[i]]=f[i-1][0][!a[i]];
		f[i][1][a[i]]=min(f[i-1][1][!a[i]],f[i-1][0][a[i]]);\/\/不修改 
		f[i][0][!a[i]]=f[i-1][0][a[i]]+c[i];
		f[i][1][!a[i]]=min(f[i-1][1][a[i]],f[i-1][0][!a[i]])+c[i];\/\/修改 
	}
	cout<<min(f[n][1][0],f[n][1][1]);
	return 0;
}