C-小美的01串翻转_牛客周赛 Round 9

题目：C-小美的01串翻转_牛客周赛 Round 9

链接：https://ac.nowcoder.com/acm/contest/63869/C

思路：

01字符串s .....,s[i-1],s[i],.....

首先我们定义f[n][2]，其中[2]表示状态位，也就是当前第i位变与不变（0表示第i位不变，1表示第i位变）

f[i][0]、f[i][1]其含义分别为以第i个字符结尾的字符串，第i位变的权值和第i位不变的权值

为了缩小问题规模，考虑第i位和第i-1位的情况：

1.若s[i]==s[i-1]，此时i和i-1这两个之间必须要变一个，可以分为以下两种情况：i不变i-1变；i变i-1不变，状态转移方程如下

f[i][0] = f[i-1][1];

f[i][1] = f[i-1][0] + 1;

2.若s[i]!=s[i-1]，此时也可以分为两种情况：i和i-1都不变；i和i-1都变，状态转移方程如下

f[i][0] = f[i-1][0];

f[i][1] = f[i-1][1] + 1;

初始状态定义为f[i-1][0] = 0;f[i-1][1] = 1; // 1表示当前为修改所以初始值为1

第i位变与不变的操作次数都能满足要求，由于题目要求选择操作次数最小，所以记录答案时取min(f[i][0],f[i][1]);

然后我们只需要枚举起始下标，记录每次不同起始下标所能求得的权值之和，最后相加即可

我们每次操作都只用到了当前位i和前一位i-1的值，所以对于f[n][2]数组来说我们只要保证当前位的前一位i-1的值是正常的即可，后续操作数据可直接覆盖也无需初始化

Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    int f[2001][2];
    long long ans = 0;
    for (int j = 0; j < n; j++)
    {
        long long sum = 0;
        f[j][0] = 0, f[j][1] = 1;
        for (int i = j + 1; i < n; i++)
        {
            if (s[i] == s[i - 1])
            {
                f[i][0] = f[i - 1][1];
                f[i][1] = f[i - 1][0] + 1;
            }
            else
            {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1] + 1;
            }
            sum += min(f[i][0], f[i][1]);
        }
        ans += sum;
    }
    cout << ans << endl;
    return 0;
}