题解：P3012 [USACO11FEB] Cowlphabet G

Zsw594188 · 2025-04-18 22:09:27 · 题解

本题可采用动态规划来解决。核心思路是用一个四维数组来记录状态，接着依据给定的合法字母对进行状态转移。

具体步骤如下：

状态定义：定义一个四维数组 dp[u][l][i][j]，其含义为当有 u 个大写字母、l 个小写字母，且当前单词的最后一个字母是 i（大写字母 i 取值范围是 0 - 25，小写字母 i 取值范围是 26 - 51），倒数第二个字母是 j 时的合法单词数量。

初始化：当 u = 0 且 l = 1 或者 u = 1 且 l = 0 时，只有一个字母，此时将 dp 数组对应位置初始化为 1。

状态转移：遍历所有合法的字母对 (a, b)，若 b 是大写字母，就更新 dp[u + 1][l][b][a] 的值；若 b 是小写字母，就更新 dp[u][l + 1][b][a] 的值。

结果计算：把所有满足有 U 个大写字母和 L 个小写字母的状态 dp[U][L][i][j] 的值累加起来，再对 97654321 取模，得到最终结果。