G. 杰哥哄对象

解法一：

朴素 DP：

易知：当前字母的改变花费只和前一个字母的值和位置有关。

很容易可以想到三维的 DP，一维代表当前的串，二维表示当前最后一个字母的值，第三维表示当前字母是在奇/偶数位置。

用 0 来表示偶数位置，1表示奇数位置。首先有 $f_{0,i,0}\leftarrow 0,i \in \Sigma$ 。

用 $S$ 表示字符串，可得：

\left \{ \begin{aligned} f_{i,j,0} \leftarrow& \min(f_{i-1,j,0}+1,f_{i-1,j,1}+[j=S_i])\\ f_{i,j,1} \leftarrow &\min_{k \in \Sigma}\{f_{i,k,0}+[j=S_i]\} \end{aligned} \right .

最后用了一个变量来记录上一个状态的最小花费，这样可以压一维枚举上一个字母的循环。

ll dp[maxn][30][2]= {0};
int main()
{
  int n=read();
  string s;
  cin>>s;
  s=" "+s;
  for(int i=1; i<=n; i++)
    for(int j=0; j<=25; j++)
    {
      for(int k=0; k<=1; k++)
      {
        dp[i][j][k]=1e8;
      }
      dp[0][j][0]=0;///偶数串
      dp[0][j][1]=1e8;///奇数串
    }
  ll minn=0;
  for(int i=1; i<=n; i++)
  {
    ll nxt_minn=1e8;
    for(int j=0; j<=25; j++)
    {
      dp[i][j][0]=dp[i-1][j][0]+1;///直接删除这个
      dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+1);///直接改变这个
      if(j==s[i]-'a'){
        dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]);///和上一个一样，不需要加一
      }
      dp[i][ s[i]-'a' ][1]=min(dp[i][s[i]-'a'][1],minn);///奇数串，直接保留
      dp[i][j][1]=min(dp[i][j][1],minn+1);///改变当前字母
      dp[i][j][1]=min(dp[i-1][j][1]+1,dp[i][j][1]);///删除当前字母
      

      nxt_minn=min(nxt_minn,dp[i][j][0]);///最小花费的合法偶数串
    }
    minn=nxt_minn;

  }
  writeln(minn);
}

解法二：

分析：根据合法串的定义，如果有两个相邻字母，我们改变一个字母和另一个字母相同的花费是 $1$ ，而直接删去两个的花费是 $2$ ，所以我们肯定不会删去两个相邻字母；同理，我们也不会同时改变两个相邻的字母。那么我们只需要考虑当前状态是通过上一个字母的状态继承过来的，还是上上个字母的状态继承过来的即可。

1表示偶数态，0表示奇数态

std:

int dp[N][2];
string a;
int main(){
  cin>>a;
  int n = a.length();
  a=" "+a;
  memset(dp, 0x3f, sizeof(dp));
  dp[1][0] = 0;
  dp[2][0] = 1;
  for (int i = 2;i <= n;++ i){
    dp[i][1] = min(dp[i][1] , dp[i - 1][0] + (a[i] != a[i - 1]));
    if(i - 2 > 0)dp[i][1] = min(dp[i][1] , dp[i - 2][0] + (a[i] != a[i - 2]) + 1);
    dp[i][0] = min(dp[i][0] , dp[i - 1][1]);
    if(i - 2 > 0)dp[i][0] = min(dp[i][0] , dp[i - 2][1] + 1);
  }
  cout << min(dp[n][1], dp[n - 1][1] + 1);
  return 0;
}

题解 | #G. 杰哥哄对象#

G. 杰哥哄对象

解法一：

解法二：

std: