ABC346D 题解

KSCD_ · 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;
}