洛谷P2697宝石串

前缀和+字符串处理即可不懂DP者的福利

#include <bits/stdc++.h>
using namespace std;
int vis[100011999];
signed main() { //稍微优化下
    ios::sync_with_stdio(0); //稍微优化下，真正赛场上还是建议scanf的
    int sum = 10000000; 
    int ans = 0;
    char x;
    int i = 1;
    while(cin>>x) {
        if(x=='G') {
            sum++; 
        } else if(x=='R'){
            sum--;
        }
        if(sum==10000000) { //没发生变化（平衡）
            ans=i;
        } else if(vis[sum]==0) {
            vis[sum] = i;  //记录结果
        } else {
            ans = max(ans,i-vis[sum]); //计算答案
        }
        i++;
    }
    std::cout<<ans<<endl;
}

洛谷P2697宝石串

原文：https://www.cnblogs.com/littlefrog/p/12220829.html