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;
}

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

tag:
动态规划，状压DP，dfs，记忆化搜索

思路：
可以是状态压缩dp，也可以是用dfs加上记忆化搜索。这里就用dfs加上记忆化搜索。用二进制来存储每一种状态，每次访问一个点就将那个点异或一下。最后每次都是返回一个答案。dp中存的是从x点开始走走到最后一个点的最短路径。

代码：

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
typedef pair<double, double> PII;
int n;
PII d[20];
bool st[20];
double dp[20][1 << 16];
double dfs(int x, int u, double step, int path)
{
    double res = 1e9;
    if (u == n)
    {
        return step;
    }
    if (dp[x][path]) return dp[x][path] + step;

    for (int i = 1; i <= n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            double tmp = sqrt(pow(d[i].first - d[x].first, 2) + pow(d[i].second - d[x].second, 2));
            res = min(res, dfs(i, u + 1, step + tmp, path | (1 << i)));
            st[i] = false;
        }
    }

    dp[x][path] = res - step;
    return res;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> d[i].first >> d[i].second;
    double res = dfs(0, 0, 0.0, 0);
    printf("%.2lf", res);
    return 0;
}