F : 吃奶酪(深搜)

F : 吃奶酪

Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 76     Solved: 17

Description

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

Input

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

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

对于全部的测试点，保证 1 ≤ n ≤ 15, |xi|, |yi| ≤ 200，小数点后最多有 3位数字。

Output

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

Sample Input

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

Sample Output

7.41

Hint

对于两个点 (x1,y1), (x2,y2)，两点之间的距离公式为 。

n 较小，可以用二进制位做标记来压缩状态进行回溯。（也可以用记忆化搜索加速）

一、题解

1、可以看到n最大是15，正常的dfs是会超时。所以这里需要用到一些剪枝技术

1. 提前算好每个点之间的距离并保存在vis[maxn][maxn]里面。减少深搜时候的计算量
2. 当这个奶酪编码dis[value][i]<=和+距离小于。那么就不用进入深搜了。continue跳过

2、参数解析

• 深搜时候使用四个参数分别代表，前一个点front、当前老鼠吃的奶酪二进制编码value
  比如：0011，就是第一、第二个奶酪被吃了。深度step用于作为终止条件、和sum，用于到终止时候求最小值。

二、AC代码

#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;
int n;
const int maxn=16;
double x[maxn],y[maxn];
double dis[1<<maxn][maxn],book[maxn],vis[maxn][maxn];
double minn=(1<<31)-1;
void dfs(int front,int value,int step,double sum)
{
    if(step==n)
    {
        minn=min(minn,sum);
        return;
    }

    for(int i=1;i<=n;i++)
    {
        if(!book[i])
        {
            int ans=value+(1<<(i-1));
            if(dis[ans][i]&&dis[ans][i]<=sum+vis[front][i])continue;
            book[i]=1;

            dis[ans][i]=sum+vis[front][i];
            dfs(i,ans,step+1,dis[ans][i]);

            book[i]=0;
        }
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }

    for(int i=0;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            vis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            vis[j][i]=vis[i][j];
        }
    }
    dfs(0,0,0,0);
    cout<<fixed<<setprecision(2)<<minn<<endl;
    return 0;
}