状态压缩DP

哈密顿路径问题：

一般设 表示  状态下，为最后一个最值情况 。

一般有两种稍微不同的写法，单纯就是写法不同，思路方法都相同。

第一个例题为第一种转移方法，有当前转移后面。

后面的都是由前面转移目前。

G. Shuffling Songs

题意：就是要你删除最少的歌曲，使其播放精彩,每对相邻的歌曲要么作者相同，要么流派相同(或两者皆有)即为精彩。

思路：观察数据范围可以发现2的16次方枚举，类似哈密顿路劲问题转移即可

string g[N], s[N];
int n;
void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> g[i] >> s[i];

    vector<int> e(n, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (g[i] == g[j] || s[i] == s[j])
                e[i] |= (1 << j);
        }
    }
    vector<vector<int>> f(1 << n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
        f[1 << i][i] = 1;

    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++) // 最后一个点是谁
        {
            if (!f[i][j])
                continue;
            for (int k = 0; k < n; k++)
            {
                if (i >> k & 1) // 加进去一个点
                    continue;
                if ((e[j] >> k) & 1)
                {
                    f[i | (1 << k)][k] = 1;
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
            if (f[i][j])
                ans = max(ans, __builtin_popcount(i));
    }
    cout << n - ans << endl;
}

AcWing 731. 毕业旅行问题

同理也是哈密顿路径问题

int g[M][M];
int f[1 << 20][20];
void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];
    memset(f, inf, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i >> j & 1)
            {
                for (int k = 0; k < n; k++)
                {
                    if (i - (1 << j) >> k & 1)
                    {
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j]);
                    }
                }
            }
        }
    }
    int ans = 1e18;
    for (int i = 1; i < n; i++)
        ans = min(ans, f[(1 << n) - 1][i] + g[i][0]);
    cout << ans << endl;
}

91. 最短Hamilton路径

int f[1 << 20][21];
int g[M][M];
void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> g[i][j];
    }
    memset(f, 0x7f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i >> j & 1)
            {
                for (int k = 0; k < n; k++)
                {
                    if (i - (1 << j) >> k & 1)
                    {
                        f[i][j] = min(f[i - (1 << j)][k] + g[k][j], f[i][j]);
                    }
                }
            }
        }
    }
    cout << f[(1 << n) - 1][n - 1] << endl;
}