题解
状态奇妙的dp题。
状态:(dp[i][a][b][c])表示匹配到(i)(注意,“匹配”表示当前目标串中所有元素仅来源于原串([1,i])中的元素,而非目标串([1,i])已被填满),已有(a)个a
、(b)个b
、(c)个c
时的变化结果数。另设(nxt[i][j])表示([i,n])中a
((j=0))、b
((j=1))、c
((j=2))出现的最小下标。
转移方程:
[dp[nxt[i][0]][a+1][b][c]+=dp[i][a][b][c]\
dp[nxt[i][1]][a][b+1][c]=dp[i][a][b][c]\
dp[nxt[i][2]][a][b][c+1]+=dp[i][a][b][c]
]
1、2、3行分别是目标串下一个元素为a,b,c
的转移方程(下一个字符只可以来源自(nxt[i]))。
目标状态:(ans=sum dp[i][a][b][c] quad (a+b+c=n,|a-b|le 1,|b-c|le 1,|a-c|le 1,1le ile n))
目标串全部填满且各字符个数相差(le 1)的状态之和。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=160,mod=51123987;
int dp[N][N/3][N/3][N/3],nxt[N][3]; char s[N];
int main()
{
int n,ans=0;
scanf("%d%s",&n,s+1);
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];
nxt[i][s[i]-'a']=i;
}
dp[1][0][0][0]=1;
int lim=(n+2)/3;
for(int i=1;i<=n;i++)
{
for(int a=0;a<=lim;a++)
{
for(int b=0;b<=lim;b++)
{
for(int c=0;c<=lim;c++)
{
if(a+b+c==n && abs(a-b)<=1 && abs(b-c)<=1 && abs(a-c)<=1) ans=(ans+dp[i][a][b][c])%mod;
dp[nxt[i][0]][a+1][b][c]=(dp[nxt[i][0]][a+1][b][c]+dp[i][a][b][c])%mod;
dp[nxt[i][1]][a][b+1][c]=(dp[nxt[i][1]][a][b+1][c]+dp[i][a][b][c])%mod;
dp[nxt[i][2]][a][b][c+1]=(dp[nxt[i][2]][a][b][c+1]+dp[i][a][b][c])%mod;
}
}
}
}
printf("%d",ans);
return 0;
}