题解 P1433 【吃奶酪】

Thaumaturge · 2019-04-14 19:55:24 · 题解

忽然发现其实可以用状压dp的思想来优化dfs...

观察数据，15个奶酪！这数据并不大，根据题意，老鼠走的路径是无后效性的，只要经过的点一致，所在的点也一致，接下来所要走的路径就是等价的

所以可以用一个二进制数来记录走过的点，另一个数记录老鼠所在的点，如果之后搜到的答案比这个点要大，就不继续搜即可，大致思想就是这样

详见代码：

#include <bits/stdc++.h>

using namespace std;

int n;
long double a[30][2],lt[30][30],zt[(1<<15)+15][18];//记录状态，第一维记录走过的点，第二维记录所在的点
long double cc1,cc2,answ;
int bj[30],i,j;

void dfs(int y,int ww,int x,long double ans){//深搜
    if(x==n+1) if(answ==0 || answ>ans) {answ=ans;return;}
    for(int g=1;g<=n;g++)
    {
        if(!bj[g])
        {
            int xb=ww+(1<<(g-1));//xb表示当前已走过的点，有标记数组挡着不用怕二进制数会进位
            if(zt[xb][g]!=0)
            if(zt[xb][g]<=ans+lt[y][g]) continue;//如果生成的路径长度比之前的还要长就不对该点继续dfs
            bj[g]=1;//标记
            zt[xb][g]=ans+lt[y][g];//记录状态
            dfs(g,xb,x+1,zt[xb][g]);//继续往下搜
            bj[g]=0;//回溯
        }
    }
    return;
}

int main(){
    cin>>n;
    a[0][0]=0;a[0][1]=0;
    for(i=1;i<=n;i++)
    {
        scanf("%Lf %Lf",&a[i][0],&a[i][1]);
        for(j=0;j<i;j++)//对两点距离初始化
        {
            cc1=a[i][0]-a[j][0];
            cc2=a[i][1]-a[j][1];
            lt[j][i]=sqrt(cc1*cc1+cc2*cc2);//记录两点距离
            lt[i][j]=lt[j][i];
        }
    }
    dfs(0,0,1,0);
    printf("%.2Lf",answ);
    return 0;
}

有个很奇怪的事，就是优化过的dfs跑第六个点比不优化的还慢，真是玄学