p1433吃奶酪-状态压缩DP

wflengxuenong · 2024-01-07 08:05:47 · 个人记录

• 题目大意： 从0点出发，不重复走过n个点的最小路径。

• 小数据，暴力或状态压缩

• 方法一： 暴力dfs+最优化剪枝

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
double dis[16][16],ans=1000000000.0,now,x[16],y[16];//两点距离，答案，现在的距离，每个点的坐标
bool vis[16];//奶酪是否被吃
void dfs(int pos,int num,double now) {
    if(now>ans)//如果现在的距离比答案大就返回
        return;
    if(num==n) {
        if(ans>now)//更新答案
            ans=now;
        return;
    }
    vis[pos]=true;
    for(int i=1; i<=n; i++) {
        if(vis[i]==false) { //枚举每个没有被吃的奶酪
            dfs(i,num+1,now+dis[pos][i]);
        }
    }
    vis[pos]=false;//回溯
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%lf%lf",&x[i],&y[i]);
    x[0]=0;
    y[0]=0;
    for(int i=0; i<=n; i++) //预处理两点距离
        for(int j=0; j<=n; j++)
            dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    dfs(0,0,0);
    printf("%0.2f",ans);
}

方法二：状压dp，填表法

#include<bits/stdc++.h>
using namespace std;

struct F{
    double x, y;
} a[20];

double dist(F a, F b)
{
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double f[20][66000];
double dis[20][20];

int n;

int main()
{
    a[0].x = 0;
    a[0].y = 0;
    memset(f, 127, sizeof(f));
    // cout<<f[0][0]<<endl;
    cin >> n;
    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++)
        {
            dis[i][j] = dist(a[i], a[j]);
        }
    }
    dis[0][0]=0; 
    for(int i=1;i<=n;i++)
    {
        f[i][(1<<(i-1))] = dis[0][i];
    }
    int End=(1<<n)-1; 
    for(int i=1;i<=End;i++)
    {
        for(int j=1;j<=n;j++)
        {

            for(int k=1;k<=n;k++)// 到了k点了 
            {
                if(j == k){continue;}//j 从k点到j点 
                if((i&(1<<(j-1)))&&(i & (1<<(k-1)))){
                    f[j][i] = min(f[j][i], f[k][i-(1<<(j-1))]+dis[k][j]);
                } 

            }
        } 
    }
    double ans = 1e20;
    for(int i=1;i<=n;i++)
    {
        ans = min(ans, f[i][((1<<n)-1)]);
    }
    printf("%.2lf",ans);
    return 0;   
} 

• 方法三，状态压缩，刷表

  
  #include<bits/stdc++.h>
  using namespace std;

struct F{ double x, y; } a[20];

double dist(F a, F b) { return sqrt((a.x-b.x)(a.x-b.x) + (a.y-b.y)(a.y-b.y)); }

double f[20][66000]; double dis[20][20];

int n;

int main() { a[0].x = 0; a[0].y = 0; memset(f, 127, sizeof(f)); // cout<<f[0][0]<<endl; cin >> n; 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++) { dis[i][j] = dist(a[i], a[j]); // dis[j][i] = dis[i][j]; // cout<<dis[i][j]<<" "; } // cout<<endl; } dis[0][0]=0; f[0][1]=0; int End=(1<<(n+1))-1; for(int i=1;i<=End;i++) { for(int j=0;j<=n;j++)//到了j点了 {

        for(int k=1;k<=n;k++)// 
        {
            if(j == k){continue;}//j 从j点到k点 
            if((i&(1<<(j)))&&(i&(1<<(k)))==0){
                f[k][i|(1<<(k))] = min(f[k][i|(1<<(k))], f[j][i]+dis[j][k]);
                int tmp=i|(1<<(k));
            } 

        }
    } 
}
double ans = 1e20;
for(int i=1;i<=n;i++)
{
    ans = min(ans, f[i][((1<<(n+1))-1)]);
}
printf("%.2lf",ans);
return 0;   

}

- 方法四：状态压缩，记忆化写法。

```cpp
#include <bits/stdc++.h>

using namespace std;

using namespace std;
const int INF = 1e9;
int n;
double x[15];
double y[15];
double dp[15][1<<15];

inline double dist( double x1 , double y1 , double x2 , double y2 ) {
    return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
}
double dfs( int now , int S ) {//s状态下，在哪个点上 
    if( dp[now][S] != -1 ) return dp[now][S];
    dp[now][S] = INF;
    for( int i = 0 ; i < n ; ++i ) {
        if( i == now ) continue;
        if( (S&(1<<i))==0 ) continue;//从i点走到now点。 
        dfs( i , S-(1<<now) );//这个点由哪个点转移而来 
        dp[now][S] = min( dp[now][S] , dp[i][S-(1<<now)] + dist( x[i] , y[i] , x[now] , y[now] ) );
    }
    return dp[now][S];
}
int main() {
    cin >> n;
    for( int i = 0 ; i < n ; ++i ) cin >> x[i] >> y[i];
    for( int i = 0 ; i < n ; ++i ) {
        for( int j = 1 ; j < (1<<n) ; ++j ) {
            dp[i][j] = -1;
        }
    }
    for( int i = 0 ; i < n ; ++i ) dp[i][1<<i] = dist(0,0,x[i],y[i]);
        double mn = INF;
    for( int i = 0 ; i < n ; ++i ) mn=min(mn,dfs( i , (1<<n)-1 ));

    printf( "%.2lf" , mn );
    return 0;
}