洛谷P1278 单词游戏

url: https://www.luogu.com.cn/problem/P1278

tag:
记忆化搜索，状压DP

思路：
记忆化搜索，dfs两个参数一个是当前的字母，另外一个是当前的状态。f[x, y] 表示当以字符串x开头是状态为y时最大的字符串长度。

代码：

#include <iostream>
#include <vector>
using namespace std;
string st[18];
vector<int> v[210];
int f[17][1 << 17];
int n, ans;
int dfs(int x, int y)
{
    if (f[x][y]) return f[x][y];
    int res = 0;
    for (auto i : v[st[x][st[x].size() - 1]])
        if (!((y>>(i - 1) & 1))) res = max(res, dfs(i, y | 1 << (i - 1)));
    return f[x][y] = res + st[x].size();
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> st[i], v[st[i][0]].push_back(i);
    for (int i = 1; i <= n; i ++) ans = max(ans, dfs(i, (1 << (i - 1))));
    cout << ans << endl;
    return 0;
}