Znzryb's Blog
0%

P1433 【吃奶酪】

Posted on Edited on

思路讲解

状压dp的整体思想就是将状态用一个数表示出来，进而方便状态转移。

1
2
double dp[25][33000];  // 状压dp数组
//      当前点  状态

那么问题就来了，怎么进行状态转移（在这题里）？

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<=(1<<n)-1;++i){     // 枚举所有状态
        for(int j=1;j<=n;++j){       // 枚举当前点
            if((i & (1<<j-1))==0)    // 说明当前点没走过,这是不合法的
                // 该操作相当于只保留了i的第j位二进制数（0，1）
                continue;
            for(int k=1;k<=n;++k){  // 枚举要去的点
                if((i & (1<<k-1))==0){
                    int status=(1<<k-1)+i;
                    dp[k][status]=min(dp[j][i]+Dis[j][k],dp[k][status]);
                }
            }
        }
    }

AC代码

https://www.luogu.com.cn/record/191940029

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;
double Loc[25][3],Dis[25][25];
double dp[25][33000];  // 状压dp数组
//      当前点  状态
// 2**15==32768,也就是用二进制下的15位数可以搞定
// 当然第十五位二进制下表示2**14 
// 一共约33000种状态

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>Loc[i][0]>>Loc[i][1];
    }
    for(int i=0;i<=n;++i){
        for(int j=0;j<=n;++j){  // 原点到不同点之间的距离也需要统计
            if(i==j)
                continue;
            double x1=Loc[i][0],y1=Loc[i][1];
            double x2=Loc[j][0],y2=Loc[j][1];
            Dis[i][j]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
        }
    }
    memset(dp, 127, sizeof(dp));   // 初始化dp为极大值
    for(int i=1;i<=n;++i)   // 初始化原点到各个点的值
        dp[i][1<<(i-1)]=Dis[0][i];
    for(int i=1;i<=(1<<n)-1;++i){     // 枚举所有状态
        for(int j=1;j<=n;++j){       // 枚举当前点
            if((i & (1<<j-1))==0)    // 说明当前点没走过,这是不合法的
                // 该操作相当于只保留了i的第j位二进制数（0，1）
                continue;
            for(int k=1;k<=n;++k){  // 枚举要去的点
                if((i & (1<<k-1))==0){
                    int status=(1<<k-1)+i;
                    dp[k][status]=min(dp[j][i]+Dis[j][k],
                        dp[k][status]);
                }
            }
        }
    }
    double ans=1e17;
    for(int i=1;i<=n;++i){
        int status=(1<<n)-1;
        ans=min(dp[i][status],ans);
    }
    cout<<setprecision(2)<<fixed<<ans<<endl;
}
// AC https://www.luogu.com.cn/record/191940029

心路历程（WA，TLE，MLE……）

前面status和点的idx位置放反了，导致了RE