洛谷P1433吃奶酪
洛谷P1433吃奶酪
原题传送：P1433
大致思路：
状压DP。这道题的状态是什么？很明显，哪些奶酪被吃了，那些没有。 那么如何划分阶段呢？目前为止吃了几块奶酪。
思路：
首先，这道题肯定要先做好毫无益处的准备工作：距离矩阵。即算出每两块奶酪之间的距离。
题目贴心的给了公式: 对于两个点(x1,y1), (x2,y2),两点之间的距离=√((χ1-x2 )^2+(y1-y2 )^2 )。
然后就可以求了：
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)d[i][j]=sqrt(pow((a[i].x-a[j].x),2)+pow((a[i].y-a[j].y),2));//d是距离矩阵
}这个题定义一个二维数组，叫f [ 状压参数 ] [ 最后吃的奶酪 ]。
这里状压参数就是一个二进制数，它的每一位分别代表下标为它的位数的奶酪是否被吃。这里先不管顺序（后面会讲）。
于是就有了状态转移方程：f[i][j]=min(f[i][j],f[i^(1<<(j-1))][k]+d[k][j])（^:异或），此时j为i的二进制形式中为1的位中的任意一数，k也一样，但j不能等于k（需枚举完）。
坑点：
老鼠一开始在(0,0)点处，要先加上(0,0)到第一个点的距离；保留2位小数输出；还有公式：√((χ_1-x_2 )^2+(y_1-y_2 )^2 )，即sqrt(pow((a[i].x-a[j].x),2)+pow((a[i].y-a[j].y),2))。对于全部的测试点，保证1≤n≤15，∣xi∣,∣yi∣≤200，小数点后最多有3位数字。（这里有个小数点后，说明这里xy坐标可以是小数。我就因为这个卡了半天80）
奉上AC代码：
不要没良心的拿了代码就走啊(再怎么说也要看完再抄啊)
#include<bits/stdc++.h>
using namespace std;
struct node{
double x,y;//……………………………………………表示每个点的x和y坐标
}a[101];//……………………………………………………题上说是15我也不一定信啊，开大一点
int n;
double d[16][16],f[1<<16][16],minn; //………………上面坑点说了xy坐标可以是小数，1<<16是因为最多有15个奶酪，我就开大一点反正也不会爆
int main()
{
cin>>n;
minn=1e8;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++) d[i][j]=sqrt(pow((a[i].x-a[j].x),2)+pow((a[i].y-a[j].y),2));//
}
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<=n;j++) f[i][j]=1e8;//………………………………赋值一个类似INF好比较
}
for(int i=1;i<=n;i++) f[(1<<(i-1))][i]=d[0][i];//上面说了要加上(0,0)到第一个点的距离
for(int i=1;i<(1<<n);i++)//………枚举所有情况（从1~(1<<n-1）就涵盖了所有情况）
{
for(int j=1;j<=n;j++)
{
if ((i&(1<<(j-1)))==0) continue;//……………如果j不在“曾经”选过的奶酪中就退
for(int k=1;k<=n;k++)
{
if ((i&(1<<(k-1)))==0) continue;//…………………同上
if (j==k) continue;
f[i][j]=min(f[i][j],f[i^(1<<(j-1))][k]+d[k][j]);
}
}
}
for(int i=1;i<=n;i++)
{
minn=min(minn,f[(1<<n)-1][i]);//…………………………………构造最优解
}
printf("%.2lf",minn);//……………………………………………………………坑点
return 0;
}