状压DP的总结

状压dp的标志

①数据小 ②通过题目所给出的条件以后得到的特征集合小

一：CF259div2 D：

题目大意：保证b[i]中每个数互质，给出a[i]，然后求1~n的abs(a[i]-b[i])最小。a[i]<=30

思路：首先得到b[i]必然小于60。这个很重要，因为我们枚举的b的集合就是60.首先当b如果都取1，那么最大的abs就是30，所以b可以取得的极限是60.然后我们可以得到60里面的所有的素数，这些素数的个数是17.因此我们发现是状压DP。

首先预处理出1~60的包含素数的集合，然后枚举a[i]，枚举1~60，再枚举1~1<<17即可得出答案。

关键：寻找子集范围，寻找变量的最大范围

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int inf = 0x3f3f3f3f;
 5 const int maxn = 100 + 5;
 6 const int u = 1 << 17;
 7 struct point{
 8     int val, x, pre;
 9 }dp[maxn][u + 5];
10 int f[maxn];
11 bool vis[maxn];
12 vector<int> v;
13 int n;
14 int a[maxn];
15 vector<int> ans;
16 
17 int main(){
18     for (int i = 2; i <= 60; i++){
19         if (!vis[i]){
20             v.push_back(i);
21             for (int j = i + i; j <= 60; j += i){
22                 vis[j] = true;
23             }
24         }
25     }
26     int len = v.size();
27     //f[1] = 1;如果单独变成1了，那么dp时就无法有多个1了。
28     for (int i = 1; i <= 60; i++){
29         int tmp = i;
30         for (int j = 0; j < len; j++){
31             bool flag = false;
32             while (tmp % v[j] == 0){
33                 tmp /= v[j];
34                 flag = true;
35             }
36             if (flag) f[i] |= 1 << (j);
37         }
38     }
39     scanf("%d", &n);
40     for (int i = 1; i <= n; i++) scanf("%d", a + i);
41     for (int i = 0; i < u; i++) dp[0][i].val = 0;
42     for (int i = 1; i <= n; i++){
43         for (int j = 0; j < u; j++){
44             dp[i][j].val = inf;
45         }
46     }
47     for (int i = 1; i <= n; i++){
48         for (int j = 1; j <= 60; j++){
49             int x = f[j];
50             for (int k = 0; k < u; k++){
51                 if (k & x) continue;
52                 if (dp[i][k | x].val > dp[i - 1][k].val + abs(a[i] - j)){
53                     dp[i][k | x].val = dp[i - 1][k].val + abs(a[i] - j);
54                     dp[i][k | x].pre = k;
55                     dp[i][k | x].x = j;
56                 }
57             }
58         }
59     }
60 
61     int pre = 0, mini = dp[n][0].val;
62     for (int i = 1; i < u; i++){
63         if (mini >= dp[n][i].val){
64             mini = dp[n][i].val;
65             pre = i;
66         }
67     }
68     //printf("%d
", dp[n][u - 1].val);
69     for (int i = n; i > 0; i--){
70         ans.push_back(dp[i][pre].x);
71         pre = dp[i][pre].pre;
72         //printf("dp[i][pre].pre = %d
", dp[i][pre].pre);
73         //printf("pre = %d
", pre);
74     }
75     reverse(ans.begin(), ans.end());
76     len = ans.size();
77     for (int i = 0; i < len; i++){
78         printf("%d%c", ans[i], i == len - 1 ? '
' : ' ');
79     }
80     return 0;
81 }

View Code

然后上面的这个47-59行可以有优化成

for (int i = 1; i <= n; i++){
        for (int j = 1; j <= 60; j++){
            int y = ((~f[j]) & (u - 1));
            int x = f[j];
            for (int k = y; ; k = (k - 1) & y){
                if (dp[i][k | x].val > dp[i - 1][k].val + abs(a[i] - j)){
                    dp[i][k | x].val = dp[i - 1][k].val + abs(a[i] - j);
                    dp[i][k | x].pre = k;
                    dp[i][k | x].x = j;
                }
                if (k == 0) break;
            }
        }
    }

View Code

就是先筛选出其中本来就不包含和原子集取&的元素，然后通过枚举k，再&可以消去很多种情况，大大减少时间复杂度。