P1278 单词游戏

P1278 单词游戏

显然一个单词的有效信息只有开头字母、结尾字母和它的长度。考虑到 n 的范围很小，可以使用记忆化搜索。记 f[x][vis] 为当前在字母 x 的位置上，已经经过了 vis 的点的最长长度。

查看代码

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
const map <char, int> num = { {'A', 1},{'E', 2},{'I', 3},{'O', 4},{'U', 5} };
const int N = 6, M = 22;
int m, n, f[N][1 << M];
int idx, hd[N], nxt[M], edg[M], wt[M];
void add(int a, int b, int c)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
}
int dfs(int x, int vis)
{
    if (f[x][vis])
        return f[x][vis];
    int ans = 0;
    for (int i = hd[x]; i; i = nxt[i])
        if (!((vis >> i) & 1))
            ans = max(ans, dfs(edg[i], vis | (1 << i)) + wt[i]);
    f[x][vis] = ans;
    return ans;
}
int main()
{
    string s;
    cin >> m;
    n = 5;
    for (int i = 1; i <= m; i++)
    {
        cin >> s;
        add(num.at(s[0]), num.at(s[s.size() - 1]), s.size());
    }
    for (int i = 1; i <= n; i++)
        add(0, i, 0);
    cout << dfs(0, 0);
    return 0;
}