题解 P7541 [COCI2009-2010#1] DOBRA

251Sec · 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;
}