题解 | 小美的01串翻转

第一眼此题可能是一个经典的区间dp，即dp[l][r][1],dp[l][r][0]，

l，r代表区间，i代表位于r上的位置是否变换,dp的值代表这段区间的权值和

状态转移如下：

for(int i=l+1;i<=r;i++){

if(s[i]!=s[i-1]){

dp[l][i][0]=dp[l][i-1][0];

dp[l][i][1]=dp[l][i-1][1]+1;

}else{dp[l][i][0]=dp[l][i-1][1];dp[l][i][1]=dp[l][i-1][0]+1;

}

1. }res+=min(dp[l][r][0],dp[l][r][1]);

}

}

但是超时，注意到，dp[l][i][0]/dp[l][i][1]的值只与i-1有关，所以：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    long long res = 0;
    for (int l = 0; l < n; l++) {
        int f0 = 0, f1 = 1;
        for (int r = l + 1; r < n; r++) {
            int nf0, nf1;
            if (s[r] != s[r - 1]) {
                nf0 = f0;
                nf1 = f1 + 1;
            } else {
                nf0 = f1;
                nf1 = f0 + 1;
            }
            f0 = nf0;
            f1 = nf1;
            res += min(f0, f1);
        }
    }

    cout << res;
    return 0;
}