状态压缩DP

哈密顿路径问题:

一般设f[i][j] 表示 i 状态下,j为最后一个最值情况 。

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

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

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

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

相关推荐

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 06:48:03       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 06:48:03       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 06:48:03       8 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 06:48:03       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 06:48:03       7 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 06:48:03       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-03 06:48:03       10 阅读

热门阅读

  1. 第八章:k8s如何使用 Service 暴露你的应用

    2024-04-03 06:48:03       5 阅读
  2. 【Vue】创建vue3项目

    2024-04-03 06:48:03       6 阅读
  3. Python可视化概率统计和聚类学习分析生物指纹

    2024-04-03 06:48:03       4 阅读
  4. LeetCode //C - 1146. Snapshot Array

    2024-04-03 06:48:03       7 阅读
  5. 利用pandas进行数据行转列和列转行

    2024-04-03 06:48:03       4 阅读
  6. Vue组件基础详细介绍

    2024-04-03 06:48:03       6 阅读