04 状态压缩DP：吃奶酪+Vitamin

吃奶酪

题目描述

房间里放着 $n$ 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 $(0,0)$ 点处。

输入格式

第一行有一个整数，表示奶酪的数量 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行两个实数，第 $(i + 1)$ 行的实数分别表示第 $i$ 块奶酪的横纵坐标 $x_i, y_i$。

输出格式

输出一行一个实数，表示要跑的最少距离，保留 $2$ 位小数。

样例 #1

样例输入 #1

4
1 1
1 -1
-1 1
-1 -1

样例输出 #1

7.41

提示

数据规模与约定

对于全部的测试点，保证 $1\leq n\leq 15$，$|x_i|, |y_i| \leq 200$，小数点后最多有 $3$ 位数字。

提示

对于两个点 $(x_1,y_1)$，$(x_2, y_2)$，两点之间的距离公式为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

---

$2022.7.13$：新增加一组 $\text{Hack}$ 数据。

本题使用状态压缩动态规划：状态压缩DP用于解决N小于21的图论问题（本身需要搜索解决的）

理解状压DP：

DP[ j ][ S ]表示已走过S的二进制表示的路径，目前终点为 j ；

比如S是00110101表示已走过第一个点，第三个点，第五个点，第六个点。
而假如所给输入一共有n个点，单独表示第一个点记为1<<0,单独表示第二个点记为1<<1由此类推单独表示第n个点为1<<(n-1)，表示已经走过n个点中所有的点，为(1<<n)-1因此，最外层循环枚举 00000000~11111111这所有的情况

核心部分代码：

for(int S=1;S<(1<<n);S++)//S
    for(int i=1;i<=n;i++)//i
       if(S & (1<<(i-1)))//2
          for(int j=1;j<=n;j++)
              if (!(S & (1 << (j - 1))) && G[i][j]!=-1)//3
                 dp[j][S | (1 << (j - 1))] = min(dp[j][S | (1 << (j - 1))] , dp[i][S] + G[i][j]);

状态转移方程为：

if(S的j-1项为0) ：

dp[j][S的j-1项置1]=minE(i from 1 to n and S的第i项为1) {dp[i][S]+G[i][j]}其中G为邻接表

总体思路：

以j为终点

枚举每个可能的i 到 j，所需要的权值，求最小；

//S的一层循环提供了每个可能的已走过的路径：

//i一层循环枚举了目前处于第i个点，但是第i个点不一定在当前的S状态下被走过，所以我们需要判断语句//2，来知晓是否被走过，如果没被走过，则不用再往下考虑。

S&(1<<(i-1)) 表示S从右往左数第（i-1）位为1；

为什么要i-1，因为我们想最大化利用空间，S最右边是第零位，即S=00000001 = =1<<(1-1)以此类推；

//j这层循环中枚举了每个在当前的S的状态下，还未到达过的点，即S为0的位置，//3处判断表示当前已走过路径的S的（j-1）位未走过（即为0），并且G[i][j]!=-1表示当前枚举的i可以到达j，G是一个整体的邻接表。

接下来填充dp[ j ][ S | (1 << ( j - 1 ) ) ]位置的数字，即dp当中，以j位置结尾，已走过路径为当前的S在第（j-1）位加上1，即路径上的第j位表示走过 的数字等于每一个以i结尾，已走过路径为S的dp表格值加上i到j的权值的和的最小值，于是，我们求出整个dp表格

最后关于如何寻找最值位置的问题：

for(int i=1;i<=n;i++)
    {
        ans = ans > dp[i][(1 << n) - 1] ? dp[i][(1 << n) - 1] : ans;
    }

ans为输出的最短路径规划，遍历每一个终点，寻找走过（1<<n）-1即走过11111111的路径的所有终点状态，即找以1号位置结尾的11111111，以2号位置结尾的11111111········

于是，我们求出了答案；

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
#define maxsize 17
double dp[16][66000];//n最大值为15，因此取2的15次方大小，为了保险我取了16次方
int main()
{
    int n;
    double x[maxsize]={0},y[maxsize]={0},G[maxsize][maxsize]={0};
    cin>>n;
    for(int i=0;i<maxsize;i++)
    for(int j=0;j<maxsize;j++)
    G[i][j]=-1;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            G[i][j] =G[j][i]= sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
        }

    for(int i=0;i<16;i++)
        for(int j=0;j<66000;j++)
        {
            dp[i][j]=DBL_MAX;
        }
    for(int i=1;i<=n;i++)
    {
        dp[i][1 << (i-1)] = sqrt((x[i]) * (x[i]) + (y[i]) * (y[i]));
    }
    for(int S=1;S<(1<<n);S++)
    {
        for(int i=1;i<=n;i++)
        {
            if(S & (1<<(i-1)))
            {
                for(int j=1;j<=n;j++)
                {

                     if (!(S & (1 << (j - 1))) && G[i][j]!=-1)
                        {
                            dp[j][S | (1 << (j - 1))] = dp[j][S | (1 << (j - 1))] > dp[i][S] + G[i][j] ? dp[i][S] + G[i][j] : dp[j][S | (1 << (j - 1))];
                        }
                }
            }
        }
    }
    double ans=INT_MAX;
    for(int i=1;i<=n;i++)
    {
        ans = ans > dp[i][(1 << n) - 1] ? dp[i][(1 << n) - 1] : ans;
    }
    printf("%.2lf",ans);
    return 0;
}

上面的题目是对图论的dp方法，下面的例题显然可以看出的状压dp

Vitamins

题面翻译

数据有$n$组数,每组数有一个价值$c_i$和一个字符串S,字符串S中包含3个字母A,B,C，问集齐ABC三个字母的最小价值（一个字母可以有多个）

样例 #1

样例输入 #1

4
5 C
6 B
16 BAC
4 A

样例输出 #1

15

样例 #2

样例输入 #2

2
10 AB
15 BA

样例输出 #2

-1

样例 #3

样例输入 #3

5
10 A
9 BC
11 CA
4 A
5 B

样例输出 #3

13

样例 #4

样例输入 #4

6
100 A
355 BCA
150 BC
160 AC
180 B
190 CA

样例输出 #4

250

样例 #5

样例输入 #5

2
5 BA
11 CB

样例输出 #5

16

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
#define maxsize 1005
#define int long long
int c[maxsize] = {0}, a[maxsize] = {0}, dp[10] = {0};
void mark(int x, string s)
{
    for (int i = 0; i < s.size(); i++)
    {
        a[x] = a[x] | (1 << ((long long)s[i] - 65));
    }
}
signed main()

{
    int n;
    string s;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> c[i] >> s;
        mark(i, s);
    }
    for (int j = 0; j < 10; j++)
    {
        dp[j] = LONG_LONG_MAX / pow(10, 10);
    }

    for (int i = 1; i <= n; i++)
    {
        dp[0] = 0;
        for (int st = (1 << 3) - 1; st >= 0; st--)
        {
            dp[st | a[i]] = min(dp[st | a[i]], dp[st] + c[i]);
        }
    }
    if (dp[(1 << 3) - 1] == (long long)(LONG_LONG_MAX / pow(10, 10)))
        dp[(1 << 3) - 1] = -1;

    cout << dp[(1 << 3) - 1] << endl;
    return 0;
}

第一次实现了状压dp可视化！！！！