状态压缩 笔记

棋盘式的f[i][j]中表示状态的j可以是状态本身也可以是在合法状态state中的下标

用状态本身比较方便，用下标比较省空间

用下标的话可以开id[M]数组记录一下

蒙德里安的梦想

求把 N×M的棋盘分割成若干个 1×2的长方形，有多少种方案。

例如当 N=2，M=4时，共有 5 种方案。当 N=2，M=3时，共有 3 种方案。

如下图所示：

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 N和 M。

当输入用例 N=0，M=0时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

1≤N,M≤11

输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
0
1
2
3
5
144
51205

先放横着的，空位竖着的就只有一种摆法

f[i][j]表示前i-1列已摆好，j表示第i列中有哪些行是凸出来的

核心思路是看第i-1行是否合法 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 12, M = 1 << 11;int n, m;
ll f[N][M];//前i-1列已摆好，第i列中有哪些行是凸出来的 
vector<int> state[M];
bool st[M];int main()
{IOSwhile(cin >> n >> m, n){for(int i = 0; i < 1 << n; i ++)//处理合法状态 {st[i] = true;int cnt = 0;for(int j = 0; j < n; j ++){if(i >> j & 1){if(cnt % 2){st[i] = false;break;}cnt = 0;}else cnt ++;}if(cnt % 2)st[i] = false;}for(int i = 0; i < 1 << n; i ++) {state[i].clear();for(int j = 0; j < 1 << n; j ++){if((i & j) == 0 && st[i | j]){state[i].push_back(j);}}}memset(f, 0, sizeof f);f[0][0] = 1;for(int i = 1; i <= m; i ++){for(int j = 0; j < 1 << n; j ++)//i-1 i{for(auto k : state[j])//i-2 i-1{//核心是看i-1列是否合法 f[i][j] += f[i - 1][k];}}}cout << f[m][0] << endl;}return 0;
}

最短Hamilton路径

给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 00 到 n−1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 n。

接下来 n行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。

对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x]并且 a[x,y]+a[y,z]≥a[x,z]。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

1≤n≤20
0≤a[i,j]≤1e7

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

 f[state][j]，state表示哪些点走过，j表示当前停留在哪个点

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 20, M = 1 << N;int n;
int f[M][N], w[N][N];int main()
{IOScin >> n;for(int i = 0; i < n; i ++)for(int j = 0; j < n; j ++)cin >> w[i][j];memset(f, 0x3f, sizeof f);f[1][0] = 0;for(int i = 0; i < 1 << n; i ++){for(int j = 0; j < n; j ++)//到第j位 {if(i >> j & 1){int t = i - (1 << j);//去掉第j位 for(int k = 0; k < n; k ++)//从k转移 {if(t >> k & 1){f[i][j] = min(f[i][j], f[t][k] + w[k][j]);}}}}}cout << f[(1 << n) - 1][n - 1];return 0;
} 

小国王

在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。

输入格式

共一行，包含两个整数 n 和 k。

输出格式

共一行，表示方案总数，若不能够放置则输出00。

数据范围

1≤n≤10,
0≤k≤n^2

输入样例：

3 2

输出样例：

16

 f[i][j][k]表示前i层，第i层状态为k，摆了j个国王

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 12, M = 1 << 10, K = 110;int n, k;
ll f[N][K][M];
vector<int> state;
vector<int> head[M];
bool st[M];
int cnt[M];bool check(int x)
{for(int i = 0; i < n; i ++){if(x >> i & 1 && x >> i + 1 & 1)return false;}return true;
}int count(int x)
{int res = 0;while(x){if(x & 1)res ++;x >>= 1;}return res;
}int main()
{IOScin >> n >> k;for(int i = 0; i < 1 << n; i ++){if(check(i)){state.push_back(i);st[i] = true;cnt[i] = count(i);}}for(auto a : state){for(auto b : state){if((a & b) == 0 && st[a | b]){head[a].push_back(b);}}}f[0][0][0] = 1;for(int i = 1; i <= n + 1; i ++)//10{for(int j = 0; j <= k; j ++)//100{for(auto a : state)//1000{for(auto b : head[a])//1000{if(j >= cnt[a])f[i][j][a] += f[i - 1][j - cnt[a]][b];}}}}cout << f[n + 1][k][0];return 0;
}

玉米田

农夫约翰的土地由 M×N个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第 11 行包含两个整数 M 和 N。

第 2..M+1 行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。

输出格式

输出总种植方法对 108108 取模后的值。

数据范围

1≤M,N≤12

输入样例：

2 3
1 1 1
0 1 0

输出样例：

9

 和上一题几乎一模一样

没了个数的限制，更简单一点

只是多了一个肥沃土地的限制，dp过程中判断即可

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 14, M = 1 << 12, mod = 100000000;int n, m;
int f[N][M];
vector<int> state, head[M];
bool st[M];
int g[N];bool check(int x)
{for(int i = 0; i < m; i ++){if(x >> i & 1 && x >> i + 1 & 1){return false;}}return true;
}int main()
{IOScin >> n >> m;for(int i = 1; i <= n; i ++){for(int j = 0; j < m; j ++){int x;cin >> x;g[i] += !x << j;}}for(int i = 0; i < 1 << m; i ++){if(check(i)){state.push_back(i);st[i] = true;}}for(auto a : state){for(auto b : state){if((a & b) == 0){head[a].push_back(b); }}}f[0][0] = 1;for(int i = 1; i <= n + 1; i ++){for(auto A : state){for(auto B : head[A]){ if(g[i] & A)continue;if(g[i - 1] & B)continue;//这两条语句任意保留一条都能过，只保留第一条是保证当前合法才转移，当前不合法就没有值//只保留第二条是保证上一行状态合法，只从合法状态转移过来，不合法虽然有值但不会被转移f[i][A] = (f[i][A] + f[i - 1][B]) % mod;}}}cout << f[n + 1][0];return 0;
}

炮兵阵地

司令部的将军们打算在 N×M的网格地图上部署他们的炮兵部队。

一个 N×M的地图由 N行 M列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。

从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入格式

第一行包含两个由空格分割开的正整数，分别表示 N 和 M；

接下来的 N 行，每一行含有连续的 M 个字符(P 或者 H)，中间没有空格。按顺序表示地图中每一行的数据。

输出格式

仅一行，包含一个整数 K，表示最多能摆放的炮兵部队的数量。

数据范围

N≤100,M≤10

输入样例：

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出样例：

6

f[i][j][j]表示第i行，第i-1行状态为j，第i行状态为k， 状态表示为最大个数。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 110, M = 1 << 10;int n, m;
int g[N];
vector<int> state;
int f[2][M][M];
int cnt[M];bool check(int x)
{for(int i = 0; i < m; i ++){if(x >> i & 1 && (x >> i + 1 & 1 || x >> i + 2 & 1)){return false;}}return true;
}int count(int x)
{int res = 0;while(x){if(x & 1)res ++;x >>= 1;}return res;
}int main()
{IOScin >> n >> m;for(int i = 1; i <= n; i ++){for(int j = 0; j < m; j ++){char c;cin >> c;if(c == 'H')g[i] += 1 << j;}}for(int i = 0; i < 1 << m; i ++){if(check(i)){state.push_back(i);cnt[i] = count(i);}}for(int i = 1; i <= n + 2; i ++){for(auto a : state)//i - 2{for(auto b : state)//i - 1{for(auto c : state)//i{if(a & b | a & c | b & c)continue;if(c & g[i] | b & g[i - 1])continue;//和上题一样判断当前状态合法才转移f[i & 1][b][c] = max(f[i & 1][b][c], f[i - 1 & 1][a][b] + cnt[c]);}}}}cout << f[n + 2 & 1][0][0];return 0;
}

愤怒的小鸟

Kiana 最近沉迷于一款神奇的游戏无法自拔。   

简单来说，这款游戏是在一个平面上进行的。 

有一架弹弓位于 (0,0) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟， 小鸟们的飞行轨迹均为形如 y=ax2+bx 的曲线，其中 a,b 是 Kiana 指定的参数，且必须满足 a<0。

当小鸟落回地面（即 x 轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有 n 只绿色的小猪，其中第 i 只小猪所在的坐标为 (xi,yi)。 

如果某只小鸟的飞行轨迹经过了 (xi, yi)，那么第 i 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行； 

如果一只小鸟的飞行轨迹没有经过 (xi, yi)，那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。 

例如，若两只小猪分别位于 (1,3) 和 (3,3)，Kiana 可以选择发射一只飞行轨迹为 y=−x2+4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。 

而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。 

这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个这个游戏。   

这些指令将在输入格式中详述。 

假设这款游戏一共有 T个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。  

由于她不会算，所以希望由你告诉她。

注意:本题除 NOIP 原数据外，还包含加强数据。

输入格式

第一行包含一个正整数 T，表示游戏的关卡总数。

下面依次输入这 T 个关卡的信息。

每个关卡第一行包含两个非负整数 n,m，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。

接下来的 n 行中，第 i 行包含两个正实数 (xi,yi)，表示第 i 只小猪坐标为 (xi,yi)，数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果 m=0，表示 Kiana 输入了一个没有任何作用的指令。

如果 m=1，则这个关卡将会满足：至多用 ⌈n/3+1⌉ 只小鸟即可消灭所有小猪。

如果 m=2，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 ⌊n/3⌋ 只小猪。

保证 1≤n≤18，0≤m≤2，0<xi,yi<10，输入中的实数均保留到小数点后两位。

上文中，符号 ⌈c⌉ 和 ⌊c⌋ 分别表示对 c 向上取整和向下取整，例如 ：⌈2.1⌉=⌈2.9⌉=⌈3.0⌉=⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。

输出格式

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。

数据范围

输入样例：

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

输出样例：

1
1

 首先m没用

爆搜的思想是传进来一个状态，找到没被覆盖的一个点，枚举能覆盖这个点的抛物线，再搜新状态

这里状压是对爆搜的优化

path[i][j]表示经过i、j两点的抛物线经过了哪些点

f[i]表示爆搜传进来的状态返回的值

对dp过程中只搜一个点而不是搜所有未被覆盖的点的解释：

四个点，如果最优解是选12和34，如果先选12，会先更新成1100，走到1100时再更新成1111，如果先选34，会先更新成0011，走到0011时再更新成1111，更新的顺序与结果无关，不管选哪个点都不会影响状态的遍历
而且一定是由小值更新大值的

这样复杂度会在原来的基础上乘以一个

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;
typedef pair<double, double> PDD;const int N = 18, M = 1 << 18;
const double eps = 1e-6;int n, m;
int f[M];
int path[N][N];//i j两个点之间经过哪些点
PDD dot[N];int cmp(double x, double y)
{if(fabs(x - y) < eps)return 0;if(x < y)return -1;return 1;
}void solve()
{cin >> n >> m;memset(path, 0, sizeof path);memset(f, 0x3f, sizeof f);f[0] = 0;for(int i = 0; i < n; i ++){cin >> dot[i].first >> dot[i].second;}//处理pathfor(int i = 0; i < n; i ++){path[i][i] = 1 << i;for(int j = 0; j < n; j ++){double x1 = dot[i].first, y1 = dot[i].second;double x2 = dot[j].first, y2 = dot[j].second;if(!cmp(x1, x2))continue;//不能横坐标相等 double a = (y1 / x1 - y2 / x2) / (x1 - x2);double b = y1 / x1 - a * x1;if(a >= 0)continue;//抛物线要开口向下 int state = 0;for(int k = 0; k < n; k ++){double x = dot[k].first, y = dot[k].second;if(!cmp(a * x * x + b * x, y)){state += 1 << k;}} path[i][j] = state;}} for(int i = 0; i + 1 < 1 << n; i ++){int x = -1;for(int j = 0; j < n; j ++){if(!(i >> j & 1)){x = j;break;}}for(int j = 0; j < n; j ++){f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);}}cout << f[(1 << n) - 1] << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}

宝藏

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋，也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。 

小明决心亲自前往挖掘所有宝藏屋中的宝藏。

但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。 

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。

已经开凿出的道路可以任意通行不消耗代价。

每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。

另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是：  

这条道路的长度 ×× 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。 

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

输入格式

第一行两个用空格分离的正整数 n 和 m，代表宝藏屋的个数和道路数。

接下来 m 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为 1∼n），和这条道路的长度 v。

输出格式

输出共一行，一个正整数，表示最小的总代价。

数据范围

1≤n≤12,
0≤m≤1000,
v≤5∗1e5

输入样例：

4 5 
1 2 1 
1 3 3 
1 4 1 
2 3 4 
3 4 1 

输出样例：

4

 朴素dp有三维dp[i][j][k],第一维是整体的状态(有哪些点),第二维是最后一层的状态，第三维是倒数第二层的状态。但这样时间复杂度和空间复杂度过于爆炸，不能这样。

最后一层只能连向最后一层的限制我们可以换成最后一层可以连上上面任意一层（乘的那个层数不变），设前者状态为A,后者状态为B

B能取到的点范围大于A，所以能去到的最小值也会<=A，所以最终结果min(A)>=min(B)

B最后的结果肯定是一颗树的形式，以下图为例，设最小的形式是这个，假设3能取到的最小的点不在倒数第二层而是在第一层（也就是1），层数k * 路长d，d会变小，乘积也会变小，但如果3接到第二层，就会变成  (k-1)*更小的那个d  ，乘积进一步变小，说明这反而就不是最小值了，就矛盾了，所以假设不成立，最小的点就在倒数第二层。而这个最终的状态是符合A的，B的最小值在A之内，得证min(A) <= min(B);

min(A)>=min(B)的同时min(A)<=min(B),证得min(A) = min(B)。

但只是计算最小值可以这样。

说得简单点就是，emm，还是以上图为例，比如3最合适的是连1，应当连在第二层，但现在连在了第三层，距离乘了2，如果连到第二层的话会乘1，这个乘1绝对是符合A状态的，乘2虽然不符合A状态，但他的值绝对是大于等于那个乘1的，两种情况都会枚举到，所以无所谓，只要包含了那个最小值就行。怎么说呢，就是那种散弹枪开一百枪，有一枪打得中就ok

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 12, M = 1 << 12, INF = 0x3f3f3f3f;int n, m; 
int f[M][N];//整体状态为i,层数为j  第0层也算一层 
int d[N][N], g[N][M];//点i到状态j的最短距离 int main()
{IOScin >> n >> m;memset(d, 0x3f, sizeof d);for(int i = 0; i < m; i ++){int a, b, c;cin >> a >> b >> c;a --, b --;d[a][b] = d[b][a] = min(d[a][b], c);}memset(g, 0x3f, sizeof g);for(int i = 0; i < n; i ++){for(int j = 1; j < 1 << n; j ++){for(int k = 0; k < n; k ++){if(j >> k & 1){g[i][j] = min(g[i][j], d[i][k]);}}}}memset(f, 0x3f, sizeof f);for(int i = 0; i < n; i ++){f[1 << i][0] = 0;}for(int i = 1; i < 1 << n; i ++){for(int  j = i - 1 & i; j; j = j - 1 & i)//枚举i的子集 {int r = i ^ j, cost = 0;for(int k = 0; k < n; k ++){if(j >> k & 1){cost += g[k][r];if(cost >= INF)break;}}if(cost >= INF)continue;for(int k = 1; k < n; k ++){if((ll)cost * k >= INF)break;f[i][k] = min(f[i][k], f[r][k - 1] + cost * k);}}}int ans = INF;for(int i = 0; i < n; i ++){ans = min(ans, f[(1 << n) - 1][i]);}cout << ans;return 0;
}