自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 22:30:51，当前版本为作者最后更新于2022-12-13 09:05:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本来不想写这题，结果打开题解区清一色的搜索……

搜索在这题复杂度的确是对的，但是这题明显很适合 DP 啊！

设状态 $f_{i,j,0/1,0/1}$，表示前 $i$ 个字符，末尾有 $j$ 个连续的辅音/元音字符（前一个 0/1），未出现/出现过 L（后一个 0/1）。

很容易推出转移方程，然后就可以快乐地转移了！复杂度 $O(n)$。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char s[105];
ll f[105][3][2][2], ans;
bool check(char c) {
	return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	f[0][0][1][0] = f[0][0][0][0] = 1;
	for (int i = 1; i <= n; i++) {
		if (s[i] == '_') {
			for (int j = 0; j <= 2; j++) {
				f[i][1][1][0] += f[i - 1][j][0][0] * 5;
				f[i][1][1][1] += f[i - 1][j][0][1] * 5;
				f[i][1][0][0] += f[i - 1][j][1][0] * 20;
				f[i][1][0][1] += f[i - 1][j][1][0] + f[i - 1][j][1][1] * 21;
			}
			f[i][2][1][0] = f[i - 1][1][1][0] * 5;
			f[i][2][1][1] = f[i - 1][1][1][1] * 5;
			f[i][2][0][1] = f[i - 1][1][0][0] + f[i - 1][1][0][1] * 21;
			f[i][2][0][0] = f[i - 1][1][0][0] * 20;
		}
		else {
			if (check(s[i])) {
				for (int j = 0; j <= 2; j++) {
					f[i][1][1][0] += f[i - 1][j][0][0];
					f[i][1][1][1] += f[i - 1][j][0][1];
				}
				f[i][2][1][0] = f[i - 1][1][1][0];
				f[i][2][1][1] = f[i - 1][1][1][1];
			}
			else {
				for (int j = 0; j <= 2; j++) {
					if (s[i] == 'L') {
						f[i][1][0][1] += f[i - 1][j][1][0];
					}
					else {
						f[i][1][0][0] += f[i - 1][j][1][0];
					}
					f[i][1][0][1] += f[i - 1][j][1][1];
				}
				if (s[i] == 'L') {
					f[i][2][0][1] += f[i - 1][1][0][0];
				}
				else {
					f[i][2][0][0] += f[i - 1][1][0][0];
				}
				f[i][2][0][1] += f[i - 1][1][0][1];
			}
		}
	}
	printf("%lld", f[n][1][0][1] + f[n][1][1][1] + f[n][2][0][1] + f[n][2][1][1]);
	return 0;
}