题解：P3012 [USACO11FEB] Cowlphabet G

这道题一看数据范围，很明显至少包含

O(UL)

，不难发现需要动态规划，其中一维是目前大写字母个数，一维是目前小写字母个数。当然还有一维是最后一个字母。

所以设

f[i][j]

表示前

i+j

个字母中，

i

个大写字母，

j

个小写字母，结尾为字母

k

的方案数。

所以设

k

为第

i

个字母，如果

k

是大写字母，转换式为

f[i][j][k]=Σf[i-1][j][

上一个

k]

；如果

k

是小写字母，转换式为

f[i][j][k]=Σf[i][j-1][

上一个

k]

。

那么我们可以拿一个 vector 来存储每个字母的上一个字母有哪些可能。

直接看代码：

CPP

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int UR=251,CR=53,mod=97654321;
vector<int> lst[CR];
int f[UR][UR][CR];
//f[i][j][k]表示前i+j个字母中，i个大写，j个小写，结尾为k的方案数
char cal(char c)
{
	if(c>='A' && c<='Z') return c-64;
	return c-70;
} 
int main()
{
	int u,l,p,i,j,m,n,ans=0;
	cin>>u>>l>>p;
	while(p--)
	{
		char a,b;
		cin>>a>>b;
		a=cal(a);
		b=cal(b);
		lst[b].push_back(a);
	}
	for(i=1;i<=26;i++) f[1][0][i]=1;
	for(i=27;i<=52;i++) f[0][1][i]=1; 
	for(i=2;i<=u+l;i++)
		for(j=0;j<=i && j<=u;j++)
		{
			int k=i-j;
			if(j>0)
				for(m=1;m<=26;m++)
					for(n=0;n<lst[m].size();n++)
						f[j][k][m]=(f[j][k][m]+f[j-1][k][lst[m][n]])%mod;
			if(k>0)
				for(m=27;m<=52;m++)
					for(n=0;n<lst[m].size();n++)
						f[j][k][m]=(f[j][k][m]+f[j][k-1][lst[m][n]])%mod;
		}
	for(i=1;i<=52;i++) ans=(ans+f[u][l][i])%mod;
	cout<<ans; 
	return 0;
}

题解：P3012 [USACO11FEB] Cowlphabet G

文章操作

相关推荐

评论

题解：P3012 [USACO11FEB] Cowlphabet G