题解：P3012 [USACO11FEB] Cowlphabet G

huangenning · 2025-10-22 00:02:35 · 题解

这道题一看数据范围，很明显至少包含 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 来存储每个字母的上一个字母有哪些可能。

直接看代码：

#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;
}