CF17C Balance

题意

【题目描述】一个仅由a,b,c三种字符组成的字符串，可以对其进行如下两种操作：

选择两个相邻字符，将第一个字符替换成第二个。

选择两个相邻字符，将第二个字符替换成第一个。这样，通过任意多次的操作，可以得到许多不同的串，为了追求字符的平衡，我们要求a,b,c三种字符在字符串中出现的次数两两之差都不能大于1。

你的任务是，统计给定字符串通过任意多次的操作，能够得到的不同的平衡串的个数。

【输入格式】

输入文件包含2行。第一行包含1个正整数n，表示字符串长度。第二行包含1个长度为n的字符串。

【输出格式】

输出共1行，包含1个正整数，表示能够得到的平衡串的数量。由于答案可能很大，因此输出时要对51123987取模。

输入输出样例

输入样例#1：

4

abca

输出样例#1：

7

输入样例#2：

4

abbc

输出样例#2：

3

输入样例#3：

2

ab

输出样例#3：

1

f[i][j][k][l]表示以第i个点开始向右扩展, 状态有j个a,k个b,l个c的方案数

因为扩展出来的序列是连续的一段

所以可以把序列中一段相同的数给看成是一个数

从这个点开始可以一直扩展到头

所以实时统计当前状态是否是合法的

如果是合法的就统计到答案里

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 155 ;
const int N = 55 ;
const int mod = 51123987 ;
using namespace std ;
int n ;
char s[M] ;
int v[M] , Nxt[M][3] , upp , Ans , f[M][N][N][N] ;
int main() {
scanf("%d",&n) ;
scanf("%s",s + 1) ;
for(int i = 1 ; i <= n ; i ++) v[i] = s[i] - 'a' ;
Nxt[n + 1][0] = Nxt[n + 1][1] = Nxt[n + 1][2] = n + 1 ;
for(int i = n ; i >= 1 ; i --) {
Nxt[i][0] = Nxt[i + 1][0] ; Nxt[i][1] = Nxt[i + 1][1] ; Nxt[i][2] = Nxt[i + 1][2] ;
    if(v[i] == 0) Nxt[i][0] = i ;
    if(v[i] == 1) Nxt[i][1] = i ;
    if(v[i] == 2) Nxt[i][2] = i ;
}
upp = n / 3 + 2 ;
f[1][0][0][0] = 1 ;
for(int i = 1 ; i <= n ; i ++)
    for(int j = 0 ; j <= upp ; j ++)
        for(int k = 0 ; k <= upp ; k ++)
            for(int l = 0 ; l <= upp ; l ++) {
            if(j + k + l == n && abs(j - k) <= 1
&& abs(j - l) <= 1 && abs(k - l) <= 1)
    Ans = (Ans + f[i][j][k][l]) % mod ;
f[Nxt[i][0]][j + 1][k][l] = (f[Nxt[i][0]][j + 1][k][l] + f[i][j][k][l]) % mod ;
f[Nxt[i][1]][j][k + 1][l] = (f[Nxt[i][1]][j][k + 1][l] + f[i][j][k][l]) % mod ;
f[Nxt[i][2]][j][k][l + 1] = (f[Nxt[i][2]][j][k][l + 1] + f[i][j][k][l]) % mod ;
}
cout << Ans << endl ;
return 0 ;
}

题意