洛谷 P1433 吃奶酪(dfs,状压dp

洛谷 P1433 吃奶酪(dfs,状压dp

洛谷 P1433 吃奶酪

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

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

如果不减枝硬搜的话会T！

完整代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <cstdio>
#include <list>
#include <queue>
#include <set>
#include <unordered_map>
#define ll long long
using namespace std;

int n;
double x[30],y[30],jl[30][30],k[(1<<15)+15][30];//x,y,两点距离，记录状态，第一维记录走过的点，第二维记录所在的点
double xx,yy,answ;
int flag[30],i,j;

void dfs(int pos,int way,int num,double ans){//当前位置，搜过的点，搜过的点数量，距离
    if(num==n+1){
        if(answ==0||answ>ans)//没有找到ans或者有更优解
        {
            answ=ans;//更新
            return;
        }
    }
    int g;
    for(g=1;g<=n;g++){
        if(flag[g]==1) continue;//走过
        int way_1=way+(1<<(g-1));  //二进制更新走过的点
        if(k[way_1][g]!=0){  //如果原先距离反而更短，很重要的减枝！
            if(k[way_1][g]<=ans+jl[pos][g]) continue;
        }
        flag[g]=1;
        k[way_1][g]=ans+jl[pos][g];
        dfs(g,way_1,num+1,k[way_1][g]);
        flag[g]=0;
    }
}

int main(){
    cin>>n;
    x[0]=0,y[0]=0;
    for(i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        for(j=0;j<i;j++){
            xx=x[i]-x[j];
            yy=y[i]-y[j];
            jl[i][j]=sqrt(xx*xx+yy*yy);
            jl[j][i]=jl[i][j];
        }
    }
    dfs(0,0,1,0);
    printf("%.2lf",answ);
}

脑壳痛！