C++11(clang++ 3.9) 解法, 执行用时: 12ms, 内存消耗: 6888K, 提交时间: 2019-07-27 09:56:30

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp1[5][100005],dp2[5][100005];
char s[100005];
int main(){
	scanf("%s",s+1);
	int l=strlen(s+1);
	for(int i=1;i<=l;i++){
		if(s[i]=='c'){
			dp1[1][i]+=1;
			dp1[2][i]+=dp1[1][i-1];
		}
		if(s[i]=='s')
			dp1[3][i]+=dp1[2][i-1];
		if(s[i]=='u')
			dp1[4][i]+=dp1[3][i-1];
		for(int j=1;j<=4;j++)
			dp1[j][i]+=dp1[j][i-1];
	}
	for(int i=l;i>=1;i--){
		if(s[i]=='c'){
			dp2[1][i]+=dp2[2][i+1];
			dp2[2][i]+=dp2[3][i+1];
		}
		if(s[i]=='s')
			dp2[3][i]+=dp2[4][i+1];
		if(s[i]=='u')
			dp2[4][i]+=1;
		for(int j=1;j<=4;j++)
			dp2[j][i]+=dp2[j][i+1];
	}
	ll ans=1e18;
	for(int i=1;i<l;i++)
		ans=min(ans,abs(dp1[4][i]-dp2[1][i+1]));
	printf("%lld\n",ans);
}

C++14(g++5.4) 解法, 执行用时: 12ms, 内存消耗: 2296K, 提交时间: 2019-07-28 14:37:26

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
const int mod=1e9+7;
long long cn[N],cn1[N];
string s;
long long c,cc,ccs,ccsu;
long long u,us,usc,q,qq,cnt,uscc;

int main(){
	cin>>s;
	int l=s.length()-1;
	for(int i=0;i<s.length();i++){
		if(s[i]=='c'){
			cc+=c;
			c++;
		}
		else if(s[i]=='s'){
			ccs+=cc;
		}else{
			ccsu+=ccs;
		}
		cn[i]=ccsu;
	}
	for(int i=l;i>=0;i--){
		if(s[i]=='u'){
			u++;
		}
		else if(s[i]=='s'){
			us+=u;
		}else{
			uscc+=usc;usc+=us;
		}
		cn1[i]=uscc;
	}
	long long ans=cn[l];
	for(int i=0;i<l;i++){
	//	cout<<cn[i]<<" "<<cn1[i]<<endl;
		ans=min(ans,abs(cn[i]-cn1[i+1]));
	}
	cout<<ans<<endl;
	
}