《基于连通性的棋盘式状态压缩dp》
因为最典型的例子是放棋盘的一类问题所以我们叫他为棋盘式：典型例子如下：https://www.acwing.com/problem/content/1066/
像这类题目如果以dfs的方式思考是不好想的，不如从上到下枚举一下到底每一行的状态到底是如何的，
因为由题目可知：第i行的棋子摆放方式与第i-2行无关，仅仅与第i-1行和第i行相邻的有关。
所以我们可以将每一行放棋子的地方看做为1，不放的地方为0，于是就有了一行的状态可以以二进制的状态表示
因为最大的状态为2^n(n为行数),本题中也就为1024（10进制下）
所以我们完全可以枚举每一行的状态，然后再由上面的状态转移过来：
我们这里的棋子模型是8面的，所以在不同的两行（假设这一行为a,上一行为b）
1.同一行上放棋子不能相邻(用代码表示：(state & (state>>1))==0 , 相当于二进制下右移了，
因为规定1旁必定是0，出现(state & (state>>1))!=0,说明不符合规定了)
2.a，b两行放棋子不能在同一列上（用代码表示： (stateA & stateB)==0,符合不在同一列上），
不能在相邻列上（用代码表示： state=(stateA | stateB),然后判断state是否有相邻的1（用上面的1方法即可））
通过上面的两个条件的筛选我们就可以除去大部分状态，然后dp即可：
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <vector>
5 using namespace std;
6 const int N = 11;
7 // dp[i][j][k]的含义是在1~i层,第i层状态为j时,总共用了k个国王而且这些国王不相互攻击的方案数；
8 int n, g;
9 long long dp[N][2 << N][N * N];
10
11 // 在我以前的小国王设计中我感受到了明显的设计问题：
12 // 1.在for循环中去判断两个状态是否合法，而不是把他封装成函数
13 // 2.其实两个状态是否合法的判断我也写的不是很好:在判断两个状态是否可以在一起，只要求|，然后判断其是否有相邻的1即可
14 // 3.不仅仅是一行上合法状态我们可以预处理出来,而且两个状态是否可以在一起我们可以预处理出来
15
16 // rstate[]是保存状态相邻无1的合法状态
17 int rstate[2 << N], icnt = 0, oneNum[2 << N];
18 vector<int> mapstate[2 << N];
19 // check()是判断枚举的状态x是否有相邻的1
20 bool check(int x)
21 {
22 return !(x & (x >> 1));
23 }
24 // 判断上下两行状态是否满足相应条件
25 int legal(int a, int b)
26 {
27 if ((a & b) == 0 && check(a | b))
28 return true;
29 else
30 return false;
31 }
32 int count(int x)
33 {
34 int res = 0;
35 for (int i = 0; i < n; i++)
36 if ((x >> i) & 1 == 1)
37 res++;
38 return res;
39 }
40 int main()
41 {
42 cin >> n >> g;
43 for (int i = 0; i < (1 << n); i++)
44 if (check(i))
45 {
46 rstate[icnt++] = i;
47 oneNum[i] = count(i);
48 }
49 for (int i = 0; i < icnt; i++)
50 for (int j = 0; j < icnt; j++)
51 if (legal(rstate[i], rstate[j]))
52 mapstate[i].push_back(rstate[j]);
53
54 //注意这里:
55 dp[0][0][0] = 1;
56 for (int i = 1; i <= n; i++)
57 for (int j = 0; j < icnt; j++)
58 {
59 int nstate = rstate[j];
60 for (int u = 0; u < mapstate[j].size(); u++)
61 {
62 int pstate = mapstate[j][u];
63 for (int k = 0; k <= g; k++)
64 if (k >= oneNum[nstate])
65 dp[i][nstate][k] += dp[i - 1][pstate][k - oneNum[nstate]];
66 }
67 }
68
69 long long res = 0;
70 for (int i = 0; i < icnt; i++)
71 {
72 res += dp[n][rstate[i]][g];
73 }
74 cout << res;
75 return 0;
76 }
再如这个题：https://www.acwing.com/problem/content/329/
与上面不同的是这个棋子是4面的，而且除了有些土地不能用之外，其他条件与上面都相同。
分析方式也一样：
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <vector>
5 using namespace std;
6 const int N = 14, MOD = 1e8;
7 // dp[i][j]:表示在前1~i-1行中种完了玉米，然后第i行的状态为j的方案数
8 int dp[N][1 << N], g[N], m, n;
9 // 这里是保存一行中合法的状态
10 vector<int> rstate;
11 vector<int> mapstate[1 << N];
12 int main()
13 {
14 cin >> m >> n;
15 for (int i = 1; i <= m; i++)
16 for (int j = 1; j <= n; j++)
17 {
18 int t;
19 scanf("%d", &t);
20 g[i] += (!t) << (j - 1);
21 }
22
23 for (int i = 0; i < 1 << n; i++)
24 if (!(i & (i >> 1)))
25 rstate.push_back(i);
26
27 // 表示在i状态下可以在其上面的j状态
28 for (int i = 0; i < rstate.size(); i++)
29 for (int j = 0; j < rstate.size(); j++)
30 if (!(rstate[i] & rstate[j]))
31 mapstate[i].push_back(j);
32
33 dp[0][0] = 1;
34 for (int i = 1; i <= m; i++)
35 for (int a = 0; a < rstate.size(); a++)
36 {
37 int nowstate = rstate[a];
38 if (!(nowstate & g[i]))
39 for (int b = 0; b < mapstate[a].size(); b++)
40 {
41 int prestate = rstate[mapstate[a][b]];
42 dp[i][nowstate] = (dp[i][nowstate] + dp[i - 1][prestate]) % MOD;
43 }
44 }
45
46 int ans = 0;
47 for (int i = 0; i < rstate.size(); i++)
48 ans = (ans + dp[m][rstate[i]]) % MOD;
49 cout << ans;
50 return 0;
51 }
《集合式状态压缩dp》
看一下n很小，可以通过两个点确定一条抛物线：注意这条这条抛物线的a<0
我们用全部确定的抛物线看一下那些点在这个上面
然后这个问题变成了：我们要选那些抛物线才可以将猪猪全部覆盖（打下来），要求抛物线选的尽可能少
这个问题其实有个学名：“重复点覆盖问题”，这里我们就不去考虑这个问题
从dfs角度上可以怎么作？
我们可以将每一个猪猪看出01，如果其中一个猪猪被打下来了，那么我们将其计为1，否则为0
于是对于n个猪猪，可以用二进制代表，全部猪猪的状态
这个就是用状态压缩表示集合
写dfs的话为：dfs(state,cnt); 表示我用了cnt个抛物线（鸟），到达了state的状态
当state==(1<<n)-1的时候就 ans=min(ans,cnt)
状态的转移为dfs(state| 这条抛物线能够打到的猪猪，cnt+1);
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <vector>
5 #include <cmath>
6 using namespace std;
7 typedef pair<double, double> PDD;
8 #define x first
9 #define y second
10 const int N = 20;
11 // 步骤：
12 // 1.首先需要根据两点求出全部可能的抛物线,然后确定每一条抛物线上的能够覆盖的点
13 // 2.然后用dfs解决重复覆盖问题;
14 int ans, n, m, t;
15 // path[i][j]用来表示过点i和点j的抛物线能过的点集
16 int path[N][N], dp[1 << N];
17 PDD pigs[N];
18 // dfs(state,cnt):表示当到达状态state时用了cnt个抛物线(鸟)
19 /* void dfs(int state, int cnt)
20 {
21 if (state == ((1 << n) - 1))
22 ans = min(ans, cnt);
23 int node;
24 // 先任选还没有被覆盖的点
25 for (int i = 1; i <= n; i++)
26 if ((state >> (i - 1))&1 == 0)
27 {
28 node = i;
29 break;
30 }
31 // 然后再枚举能够通往这个点的全部抛物线
32 for (int i = 1; i <= n; i++)
33 dfs(node | path[node][i], cnt + 1);
34 } */
但是dfs会超时，我们把dfs转换为for循环，用dp数组记录已经算到到达state状态的最小抛物线数
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <vector>
5 #include <cmath>
6 using namespace std;
7 typedef pair<double, double> PDD;
8 #define x first
9 #define y second
10 const int N = 20;
11 // 步骤：
12 // 1.首先需要根据两点求出全部可能的抛物线,然后确定每一条抛物线上的能够覆盖的点
13 // 2.然后用dfs解决重复覆盖问题;
14 int ans, n, m, t;
15 // path[i][j]用来表示过点i和点j的抛物线能过的点集
16 int path[N][N], dp[1 << N];
17 PDD pigs[N];
18 // dfs(state,cnt):表示当到达状态state时用了cnt个抛物线(鸟)
19 /* void dfs(int state, int cnt)
20 {
21 if (state == ((1 << n) - 1))
22 ans = min(ans, cnt);
23 int node;
24 // 先任选还没有被覆盖的点
25 for (int i = 1; i <= n; i++)
26 if ((state >> (i - 1))&1 == 0)
27 {
28 node = i;
29 break;
30 }
31 // 然后再枚举能够通往这个点的全部抛物线
32 for(int i=1;i<=n;i++)
33 dfs(state|path[node][i],cnt+1);
34 } */
35 int main()
36 {
37 cin >> t;
38 while (t--)
39 {
40 memset(path, 0, sizeof(path));
41 cin >> n >> m;
42 for (int i = 1; i <= n; i++)
43 scanf("%lf %lf", &pigs[i].x, &pigs[i].y);
44 for (int i = 1; i <= n; i++)
45 {
46 // 表示只过点i的抛物线
47 // 这里是解决当n==1时的边界情况
48 path[i][i] = 1 << (i - 1);
49 for (int j = 1; j <= n; j++)
50 {
51 double x1 = pigs[i].x, y1 = pigs[i].y;
52 double x2 = pigs[j].x, y2 = pigs[j].y;
53 if (fabs(x1 - x2) < 1e-8)
54 continue;
55 double a = (y1 / x1 - y2 / x2) / (x1 - x2);
56 double b = y1 / x1 - a * x1;
57 // 万分注意这里:一定要a<0才行
58 if (fabs(a - 0) < 1e-8 || a > 0)
59 continue;
60 int state = 0;
61 for (int k = 1; k <= n; k++)
62 {
63 double x3 = pigs[k].x;
64 double y3 = a * x3 * x3 + b * x3;
65 // 说明点k在这条抛物线上:
66 if (fabs(y3 - pigs[k].y) < 1e-8)
67 state += 1 << (k - 1);
68 }
69 path[i][j] = state;
70 }
71 }
72 memset(dp, 0x3f, sizeof(dp));
73 dp[0] = 0;
74 // 因为我们这里是根据dfs改成的for循环,在dfs中当state==1<<n-1时就该返回了
75 // 这里我们也一样，所以状态i不用枚举到1<<n-1;
76 for (int i = 0; i < (1 << n) - 1; i++)
77 {
78 int node;
79 for (int j = 1; j <= n; j++)
80 {
81 if (!((i >> (j - 1)) & 1))
82 {
83 node = j;
84 break;
85 }
86 }
87 // 从初状态i到达新状态用了path[node][j]这条抛物线
88 for (int j = 1; j <= n; j++)
89 dp[i | path[node][j]] = min(dp[i | path[node][j]], dp[i] + 1);
90 }
91 if (m == 1)
92 ans = (n % 3 == 0) ? n / 3 + 1 : n / 3 + 2;
93 else
94 ans = n;
95 ans = min(ans, dp[(1 << n) - 1]);
96 cout << ans << endl;
97 }
98 return 0;
99 }
标签：状态,int,压缩,----,state,抛物线,include,dp From： https://www.cnblogs.com/cilinmengye/p/16944117.html