题解：SP27381 BLKEK - Emoticon

· · 题解

题外话：这个题我之前帮叶橡皮修了题解格式来着。

一句话题意：求给定字符串中 \texttt{KEK} 子序列的数量。

设 dp_{i,1/2/3} 分别表示处理了前 i 个字符，这个前缀里 \texttt{K,KE,KEK} 作为子序列的数量。

遇到 \texttt E 的时候可以从上一位的 \texttt K 转移到 \texttt{KE}；遇到 \texttt{K} 的时候 \texttt K 直接自增，上一位的 \texttt{KE} 转移到 \texttt{KEK}。

甚至可以不开数组，滚动记录状态即可。时间复杂度线性。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int k=0,ke=0,kek=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='K')k++,kek+=ke;
            else if(s[i]=='E')ke+=k;
        }
        cout<<kek<<endl;
    }
    return 0;
}
//「船到桥头自然直嘛，再说还有专家在。」
//「打捞者又不是闯空门的小偷……」