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 ;

}

巴特西