C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 1656K, 提交时间: 2019-03-01 17:18:06

#include<bits/stdc++.h>
using namespace std;
int n;
int nxt[3][100007];
char buff[100007];
const char *seq="msc",*pat[8]={"022012","020212","002212","012022","020122","002122","010222","001222"};
int main(){
    scanf("%d%s",&n,buff);
    nxt[0][n]=nxt[1][n]=nxt[2][n]=n;
    for(int i=n-1;i>=0;i--)
        for(int j=0;j<3;j++)
            nxt[j][i]=buff[i]==seq[j]?i:nxt[j][i+1];
    long long ans=0;
    for(int i=0;i<n;i++){
        int low=n;
        for(int j=0;j<8;j++){
            int pos=i-1;
            for(int k=0;pos<n&&k<6;k++)
                pos=nxt[pat[j][k]-'0'][pos+1];
            low=min(low,pos);
        }
        ans+=n-low;
    }
    printf("%lld",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 39ms, 内存消耗: 38868K, 提交时间: 2020-03-15 19:23:42

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int inf=1e9+7;
char p[10][10]={"mscmcc","mccmsc","mmsccc","mmcscc","mmccsc","msmccc","mcmcsc","mcmscc"};
int dp[maxn][10][10];
char a[maxn];
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s",a+1);
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		int tmp=0;
		for(int j=0;j<8;j++)
		{
			for(int k=0;k<6;k++)
			{
				if(a[i]==p[j][k])
				{
					if(k==0) dp[i][j][k]=i;
					else dp[i][j][k]=dp[i-1][j][k-1];
				}
				dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
			}
			tmp=max(tmp,dp[i][j][5]);
		}
		ans+=tmp; 
	}
	printf("%lld\n",ans);
}