状压DP（c++)

好久都没来水博客了，现在闲的来写一篇刚学的状压DP思想

状压DP要把一个集合中的所有元素一一分别拿出来讨论，需要用到二进制保存集合状态

例如

110001010二进制，0代表没有，1代表有这个元素

876543210他的位置

所有状压dp差不多就一个思想

逐步将集合中的点包含进来

首先引入一道题目

洛谷P1433

题目描述

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

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

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
double a[20][20];//预处理第i块到j块的距离
double x[20],y[20];//每块的横纵坐标
double f[18][34000];//状压dp数组，在第i个点上，走过的二进制状态的十进制表达
//1100110001例如表示走过1，5，6，9，10块奶酪
//9876543210 
int n;
double dis(int v,int w)//计算两块奶酪的距离
{
    return sqrt((x[v]-x[w])*(x[v]-x[w])+(y[v]-y[w])*(y[v]-y[w]));
}
void solve() {
    int i,j,k;
    double ans;
    memset(f,127,sizeof(f));
    ans=f[0][0];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    x[0]=0;
    y[0]=0;
    for( i=0;i<=n;i++)
    {
        for( j=i+1;j<=n;j++)
        {
            a[i][j]=dis(i,j);
            a[j][i]=a[i][j];
        }
    }//初始化距离数组
    for(int i=1;i<=n;i++)//init
    {
        f[i][(1<<(i-1))]=a[0][i];//在i点上且只有经过i点时距离时原点到i点得距离
    }
    for(k=1;k<(1<<n);k++)//枚举所有二进制状态
    {
        for(i=1;i<=n;i++)//从小到大
        {
            if((k&((1<<(i-1))))==0)
            continue;
            for(j=1;j<=n;j++)//有点类似dj算法，a到b的路径可以为a->c->b
                //先取出其中包含的一个点取得路径
            {
                if(i==j)continue;
                if((k&(1<<(j-1)))==0)continue;
                f[i][k]=min(f[i][k],f[j][k-(1<<(i-1))]+a[i][j]);
            }

        }
    }
    for(int i=1;i<=n;i++)
    {
        ans=min(ans,f[i][(1<<n)-1]);
    }
    cout<<fixed<<setprecision(2)<<ans;
}
int main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}