[NOIP2017]宝藏子集DP

题面：[NOIP2017]宝藏

题面：

　　首先我们观察到，如果直接DP，因为每次转移的代价受上一个状态到底选了哪些边的影响，因此无法直接转移。

　　所以我们考虑分层DP，即每次强制现在加入的点的距离为k（可能实际上小于k），这样就可以忽略掉上个状态选了哪些边的影响了。

　　所以这样为什么是正确的呢？

　　设f[i][j]表示DP到第i层，状态为j的最小代价。（即每层离起点最远的点的距离为i - 1，所以下次转移的点距离为i）

　　那么如果一个点被错误的计算了代价，当且仅当这个点离起点的距离小于i，但我们依然按照i的距离来计算了代价。

　　那么可以证明，这个点一定会在正确的层数被计算一次（i之前的某一层），那么由于当前层数导致代价被多算，因此肯定没那么优，所以不会对答案造成影响。

　　因此我们直接DP即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define R register int
 4 #define AC 15
 5 #define ac 12000
 6 #define inf 2139062143
 7 #define LL long long
 8 
 9 int n, m, maxn, ans = inf;
10 int f[AC][ac], in[AC], g[AC][AC], dis[ac][AC];
11 
12 inline int read()
13 {
14     int x = 0;char c = getchar();
15     while(c > '9' || c < '0') c = getchar();
16     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
17     return x;
18 }
19 
20 inline void upmin(int &a, int b){
21     if(b < a) a = b;
22 }
23 
24 void pre()
25 {
26     n = read(), m = read(), maxn = (1 << n) - 1;
27     memset(g, 127, sizeof(g));
28     for(R i = 1; i <= m; i ++)
29     {
30         int a = read(), b = read(), c = read();
31         upmin(g[a][b], c), upmin(g[b][a], c);
32     }
33     int tmp = 1;
34     for(R i = 1; i <= n; i ++)
35         in[i] = tmp, tmp <<= 1, g[i][i] = 0;
36 }
37 
38 void get()//获取所有联通块到各个点的距离，预处理可以降低复杂度
39 {
40     memset(dis, 127, sizeof(dis));
41     for(R k = 1; k <= maxn; k ++)
42     {
43         for(R i = 1; i <= n; i ++)//枚举集合内的一点
44         {
45             if(!(k & in[i])) continue;
46             for(R j = 1; j <= n; j ++)
47             {
48                 if(k & in[j]) dis[k][j] = 0;
49                 else upmin(dis[k][j], g[i][j]);
50             }
51         }
52     }
53 }    
54 
55 void work()
56 {
57     memset(f, 127, sizeof(f));
58     for(R k = 1; k <= n + 1; k ++)//枚举当前层(走下一步的最远距离)
59     {
60         for(R i = 1; i <= n; i ++) f[k][in[i]] = 0;
61         upmin(ans, f[k][maxn]);    
62         for(R i = 1; i <= maxn; i ++)//枚举状态
63         {
64             if(f[k][i] == inf) continue;//不判断这个可能会爆int
65             int s = i ^ maxn;//获取补集
66             for(R j = s; j; j = (j - 1) & s)//枚举补集的子集
67             {
68                 int tmp = 0;bool flag = true;
69                 for(R l = 1; l <= n; l ++)
70                 {
71                     if(!(j & in[l])) continue;//如果不在这个子集中就跳过
72                     if(dis[i][l] == inf) {flag = false; break;}
73                     tmp += k * dis[i][l];
74                 }
75                 if(flag) upmin(f[k + 1][i | j], f[k][i] + tmp);
76             }
77         }
78     }
79     printf("%d
", ans);
80 }
81 
82 int main()
83 {
84 //    freopen("in.in", "r", stdin);
85     pre();
86     get();
87     work();
88 //    fclose(stdin);
89     return 0;
90 }

View Code

[NOIP2017]宝藏 子集DP

[NOIP2017]宝藏子集DP