第一章 动态规划(5)：状态压缩模型

目录

• 1、棋盘式DP / 基于连通性的DP
• • 1.1、蒙德里安的梦想（基本模型）（连通性：1X2矩阵）
  • 1.2、小国王（连通性：井字形）
  • 1.3、玉米田（连通性：十字型）
  • 1.4、炮兵阵地（连通性：扩展的十字型）
• 2、集合式DP
• • 2.1、最短Hamilton路径（基本模型）
  • 2.2、怒的小鸟
  • 2.3、宝藏

1、棋盘式DP / 基于连通性的DP 1.1、蒙德里安的梦想（基本模型）（连通性：1X2矩阵）

ACWing 291

算法思想：

我们先考虑横向摆放条件下，即仅摆放2x1的方块的时候，总的方案数等于只放横着的小方块的合法方案数。因为所有横放确定了，那么竖放方案是唯一的。

如何判断方案是否合法？所有剩余未知能否填充满竖直着的小方块。可以按列来看，每一列内部所有连续的空着的小方块需要是偶数个。

f[i, j]：所有摆到第i列，上一列伸出来的行的状态是j（j是一个二进制数，j ∈ (0, 2^(列数))）的情况下，即上一列有哪些行伸进第二列的情况下，总共的方案数。

对于状态转移，我们考虑第i-1个状态，有

要使状态i-1能转换为i，必须满足条件：

• 条件一：第i-1个状态和第i个状态不能冲突，即(j & k) == 0；
• 条件二：第i-1列中纵向的连续格子个数必须是偶数，即j | k不能存在奇数个0。因为我们这里考虑的是横向1x2的格子，当横向格子填完了之后，就要使用纵向2x1的格子来填，它只能填入连续个数为偶数的纵向格子。

所以状态转移方程表示为：f[i, j] += f[i-1, j]

#include 
#include 
#include 

using namespace std;

const int N = 12, M = 1 << N;

int n, m;
long long f[N][M]; // 第一维表示列，第二维表示所有可能的状态
bool st[M]; //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true

int main()
{
    while (cin >> n >> m, n || m) // 读入n和m，且n 或 m 不等于0
    {
        memset(f, 0, sizeof f);
        
        // 预处理掉所有状态存在奇数个0的情况
        for (int i = 0; i < 1 << n; i ++ )
        {
            st[i] = true;
            
            int cnt = 0; // 表示当前这一段连续0的个数   
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1) // 如果第j位为1，这一段遍历完
                {
                    if (cnt & 1) // 判断这一段中0的个数cnt是否为奇数
                        st[i] = false;
                    cnt = 0; // 这一段结束
                }
                else 
                    cnt ++ ;
            
            if (cnt & 1) // 判断你最后一段0的个数cnt是否是奇数
                st[i] = false;
        }
        
        f[0][0] = 1; // 一个都不摆，f[0][j]、f[i][0] 都不可能
        for (int i = 1; i <= m; i ++ ) // 枚举所有列，列数的下标是从0开始的，注意这里的 i
            for (int j = 0; j < 1 << n; j ++ ) // 枚举所有状态
                for (int k = 0; k < 1 << n; k ++ ) // 枚举第i-1列所有状态
                    if ((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        
        
        cout << f[m][0] << endl; // 合法状态是第 m-1 列没有伸出来到第 m 列的行
    }
    
    return 0;
}

1.2、小国王（连通性：井字形）

ACwing 1064

由题分析，因为第i行的状态只和第i-1行有关系，与1 ~ i-2行无关。

集合

f[i,j,s]：所有只摆在前i行已经放完，并且放完了j个国王，最后第i行摆放的状态是s的所有的方案数。

这里的s是一个二进制数，如果有n列，那么s是一个n位的二进制数

集合划分

根据第i-1层状态来划分，该层共有2^n中情况，要使第i-1行转移成第i行的s状态，第i-1行的状态必须满足：

• 第i-1行内部不能有两个1相邻
• 第i-1行和第i行之间也不能相互攻击到

对于第二个性质：假设第i-1行状态的值为a，第i行的值为b，那么只要满足

1. (a & b) == 0 // 同一列不能相互攻击
2. (a | b) 的结果不能存在两个相邻的 1 // 斜对角线上不能相互攻击

状态计算

1. 若两个性质都满足，由上图，那么f[i,j,b]表示已经摆完了前i排，使用了j个国王，并且第i排的状态是b，第i-1排的状态是a的所有方案。
2. 如果去掉最后一排，那么f[i-1,j-count(b),a]表示已经摆完了前i-1排，使用了j-count(b)个国王，并且第i-1排的状态是a的所有方案数。

所以计算1的方案数可以有计算2的方案数得出。

#include 
#include 

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110; // k是国王数量，这里N开到12是为了方便最后输出

int n, m; // n表示个数，m表示国王数量
vector state; // 表示所有合法的状态
int cnt[M]; // cnt存储每个状态中1的个数
vector head[M]; // 每个状态可以转移到的其它状态
LL f[N][K][M];

// 判断state中是否存在两个相邻的1
bool check(int state) {
    for (int i = 0; i < n; i++)
        if ((state >> i & 1) && (state >> (i + 1) & 1))
            return false;
    return true;
}

// 返回state中1的个数
int count(int state) {
    int res = 0;
    for (int i = 0; i < n; i++)
        res += state >> i & 1;
    return res;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < 1 << n; i++)
        if (check(i)) // 检查当前状态中是否存在两个连续的1
        {
            state.push_back(i);
            cnt[i] = count(i);
        }


    // 建立不同状态之间的转移关系
    for (int i = 0; i < state.size(); i++)
        for (int j = 0; j < state.size(); j++) {
            int a = state[i], b = state[j]; // a代表第一个状态，b代表第二个状态
            if ((a & b) == 0 && check(a | b)) // 判断是否能转移的两个条件是否满足
                head[i].push_back(j); // 将b添加到a可以转移状态的集合中去
        }

    // dp
    f[0][0][0] = 1;
    for (int i = 1; i <= n + 1; i++) // 直接摆到n+1，方便最后输出，即第n+1行一个都不摆
        for (int j = 0; j <= m; j++) // 国王的数量
            for (int a = 0; a < state.size(); a++) // 枚举所有状态
                for (int b: head[a]) // 枚举a所有能到的状态b
                {
                    int c = cnt[state[a]]; // a中1的个数
                    if (j >= c) // 每一行国王数量要小于总的国王数量上限
                        f[i][j][a] += f[i - 1][j - c][b];
                }

    cout << f[n + 1][m][0] << endl; // 第 n+1 行一个都不摆

    return 0;
}

1.3、玉米田（连通性：十字型）

ACwing 327

由题分析，因为第i行的状态只和第i-1行有关系，与1 ~ i-2行无关。

集合

f[i, s]：所有摆放了前i行，且第i行状态是s的所有摆放方案的集合

集合划分

根据第i-1层状态来划分，该层共有2^n中情况，要使第i-1行转移成第i行的s状态，第i-1行的状态必须满足：

• 第i-1行、第i行内部都不能有两个1相邻
• 第i-1行和第i行之间同一列不能同时为1，即(a & b) == 0
  

状态计算

• 已经摆完前i行，且第i行状态是a，第i-1行的状态是b的所有摆放方案
• 去掉最后一行a，则就变成
• 已经摆完前i-1行，且第i-1行的状态是b的所有摆放方案：f[i-1,b]

#include 
#include 

using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;

int n, m;
int g[N];
vector state;
vector head[M];
int f[N][M];

bool check(int state) // 检查是否存在相邻的1
{
    for (int i = 0; i + 1 < m; i ++ )
        if ((state >> i & 1) && (state >> (i + 1) & 1))
            return false;
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            int t;
            cin >> t;
            g[i] += !t * (1 << j); // t=0的时候，表示该位置不能选择，将其置为1，表示不能选择
        }
    
    // 预处理所有合法状态
    for (int i = 0; i < 1 << m; i ++ )
        if (check(i))
            state.push_back(i);
    
    // 不同合法状态之间的转移关系
    for (int i = 0; i < state.size(); i ++ )
        for (int j = 0; j < state.size(); j ++ )
        {
            int a = state[i], b = state[j];
            if ((a & b) == 0) // 判断条件
                head[i].push_back(j);
        }           
    
    // dp
    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i ++ )
        for (int j = 0; j < state.size(); j ++ )
            if (!(g[i] & state[j])) // 田地是否能种 
                for (int k : head[j]) // 枚举所有能到的状态
                    f[i][j] = (f[i][j] + f[i - 1][k]) % mod;

    cout << f[n + 1][0] << endl;
    
    return 0;
}

1.4、炮兵阵地（连通性：扩展的十字型）

ACwing 292

由题分析，因为第i行的状态不仅和第i-1行有关系，还和第i-2行有关系，与1 ~ i-3行无关。

集合

f[i,j,k]：所有已经摆完前i行，且第i-1行的状态是j，第i行的状态是k的所有摆放方案的最大值

集合划分

根据第i-2行状态来划分，该行共有2^n中情况，要使第i-2行状态c转移成第i-1行的状态b和第i行的a状态，须满足（g[i]表示第i行的地形情况）：

• 第i-2行、第i-1行、第i行同一列不能都有炮，即：((a&b)|(a&c)|(b&c)) == 0
• 炮必须放在平地上，不能放在山地上，即((g[i-1]&a)|(g[i]&b)) == 0

#include 
#include 

using namespace std;

const int N = 10, M = 1 << 10;

int n, m;
int g[110]; // g表示地图，这里地图每一行是一个二进制数来表示的
int f[2][M][M];
vector state;
int cnt[M]; // 每个数中1的个数

bool check(int state) {
    for (int i = 0; i < m; i++)
        if ((state >> i & 1) && ((state >> (i + 1) & 1) || (state >> (i + 2) & 1))) // 相邻两个炮(1表示)之间要隔两块空地
            return false;
    return true;
}

// 统计二进制数中1的个数
int count(int state) {
    int res = 0;
    for (int i = 0; i < m; i++)
		res += state >> i & 1;
    return res;
}

int main() {
    cin >> n >> m;
    
    // 读入地图
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            g[i] += (c == 'H') << j;
        }

    // 预处理每个状态是否合法
    for (int i = 0; i < 1 << m; i++)
        if (check(i)) // 判断是否合法：相邻两个炮(1表示)之间要隔两块空地
        {
            state.push_back(i);
            cnt[i] = count(i);
        }

    // dp
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < state.size(); j++) // 枚举所有合法状态
            for (int k = 0; k < state.size(); k++)// 枚举所有合法状态
                for (int u = 0; u < state.size(); u++) // 枚举倒数第二行的状态
                {
                    int a = state[j], b = state[k], c = state[u]; // a表示第i-1行状态，b表示第i行状态，c表示第i-2行状态
                    if ((a & b) | (b & c) | (a & c)) // 判断条件1
                        continue;
                    if (g[i - 1] & a | g[i] & b) // 判断条件2
                        continue;
                    // 这里使用了滚动数组，x%1后要么为1，要么为0，第i维和第i-1维数值不同，一个奇数一个偶数，所以%1后是交替滚动的
                    f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
                }

    int res = 0;
    for (int i = 0; i < state.size(); i++)
        for (int j = 0; j < state.size(); j++)
            res = max(res, f[n & 1][i][j]);

    cout << res << endl;

    return 0;
}

另外一种输出方式

#include 
#include 

using namespace std;

const int N = 10, M = 1 << 10;

int n, m;
int g[110]; // g表示地图，这里地图每一行是一个二进制数来表示的
int f[2][M][M];
vector state;
int cnt[M]; // 每个数中1的个数

bool check(int state) {
    for (int i = 0; i < m; i++)
        if ((state >> i & 1) && ((state >> (i + 1) & 1) || (state >> (i + 2) & 1))) // 相邻两个炮(1表示)之间要隔两块空地
            return false;
    return true;
}

// 统计二进制数中1的个数
int count(int state) {
    int res = 0;
    for (int i = 0; i < m; i++)
		res += state >> i & 1;
    return res;
}

int main() {
    cin >> n >> m;
    
    // 读入地图
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            g[i] += (c == 'H') << j;
        }

    // 预处理每个状态是否合法
    for (int i = 0; i < 1 << m; i++)
        if (check(i)) // 判断是否合法：相邻两个炮(1表示)之间要隔两块空地
        {
            state.push_back(i);
            cnt[i] = count(i);
        }

    // dp
    for (int i = 1; i <= n + 2; i++)
        for (int j = 0; j < state.size(); j++) // 枚举所有合法状态
            for (int k = 0; k < state.size(); k++)// 枚举所有合法状态
                for (int u = 0; u < state.size(); u++) // 枚举倒数第二行的状态
                {
                    int a = state[j], b = state[k], c = state[u]; // a表示第i-1行状态，b表示第i行状态，c表示第i-2行状态
                    if ((a & b) | (b & c) | (a & c)) // 判断条件1
                        continue;
                    if (g[i - 1] & a | g[i] & b) // 判断条件2
                        continue;
                    // 这里使用了滚动数组，x%1后要么为1，要么为0，第i维和第i-1维数值不同，一个奇数一个偶数，所以%1后是交替滚动的
                    f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
                }

    cout << f[n + 2 & 1][0][0] << endl;

    return 0;
}

2、集合式DP 2.1、最短Hamilton路径（基本模型）

ACWing 91

f(i,j)：所有从0走到j，走过的所有点存在i中的所有路径的最小值

Tips：i是一个二进制数，其中每一位表示当前这个点是否走过了。比如：i = (1110011)2，则第0、1、4、5、6几个点走过，其余点没走过。因为题中n ∈ (1, 20)，所以i ∈ (1, 2^20)。

集合划分：

• 使用倒数第2个点是哪个点来分类
• 当倒数第二个点是3的时候，f[i, j]就表示：所有从0走到j，经过的点是i，并且倒数第二个点是3的路径。
  

状态计算：

• 假设倒数第二个点是k，则总路径就表示为：0 -> k -> j。又因为路径k -> j是固定的，所以要使总路径最短，只需要0 -> k 最短即可；
• 又因为有0 -> j走过的所有的点是i中的点，所以0 -> k走过的点是i中除去j这个点；

故状态转移方程为：f(i, j) = min(f(i-{j}, k) + a[k, j])

#include 
#include 
#include 

using namespace std;

const int N = 20, M = 1 << N;

int n;
int w[N][N]; // 两点之间的距离
int f[M][N];

int main()
{
    cin >> 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; // 从0走到0，里面所包含的元素只有0一个元素的路径
    
    for (int i = 0; i < 1 << n; i ++ ) // 求每个状态
        for (int j = 0; j < n; j ++ ) // j表示走到了哪一个点
            if (i >> j & 1) //	如果第j位上位1，则第j个数被选择
                for (int k = 0; k < n; k ++ ) //k表示走到j这个点之前,以k为终点的最短距离
                    if (i >> k & 1) 
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                        
    cout << f[(1 << n) - 1][n - 1] << endl;
    
    return 0;
}

2.2、怒的小鸟

ACwing 526

普通抛物线方程： y = a x 2 + b x + c y=ax^2+bx+c y=ax2+bx+c，又因为本题抛物线必过原点且开口朝下，所以有 a < 0 ， c = 0 a<0，c=0 a<0，c=0，所以本题抛物线方程为： y = a x 2 + b x y=ax^2+bx y=ax2+bx，仅需两个点就可以确定抛物线。又因为抛物线上任意一点的斜率 y ′ = 2 a x + b < + ∞ y^{'}=2ax+b < +infty y′=2ax+b<+∞，若两个点是在同一垂直直线上的话，两个点的斜率就等于 + ∞ +infty +∞，这是不可能事件。故：本题抛物线方程为 y = a x 2 + b x y=ax^2+bx y=ax2+bx，仅需两个横坐标不相同的点就可以确定抛物线。 因为本题有 n n n个点，所以总共会有 n 2 n^2 n2根抛物线。所以我们可以先将每条抛物线预处理出来，并且求出每条抛物线能够覆盖哪些点。这里问题就转换成了：给我们很多条抛物线，问可以选择多少条最少的抛物线覆盖所有的点 （重复覆盖问题）。

假定给我们一个 n × n ntimes n n×n 的 01 矩阵
重复覆盖问题：问可以使用最少多少行，使每一列都至少包含一个1。比如愤怒的小鸟。
精确覆盖问题：问可以使用最少多少行，使每一列仅包含一个1。比如八皇后，数独。
最优解法：DancingLink 算法。（本题使用集合类型的状态压缩DP来优化暴力搜索解决问题）

已知两点 ( x 1 , y 1 ) 、 ( x 2 , y 2 ) (x_1,y_1)、(x_2,y_2) (x1​,y1​)、(x2​,y2​) 求抛物线方程 y = a x 2 + b x y=ax^2+bx y=ax2+bx

#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PDD;

const int N = 18, M = 1 << 18;
const double eps = 1e-8; // 浮点数误差容忍度

int n, m;
PDD q[N]; // 存储每只猪的坐标
int path[N][N]; // path[i][j] 表示第i个点和第j个点构成的抛物线能覆盖的点的状态
				// 比如：path[2][3] = 100111 表示由2号猪和3号猪确定的抛物线可以消灭编号1，2，3，6的小猪
int f[M]; // f[i] 表示当前击败状态i表示的小猪所需要的最少的小鸟；当前点集覆盖状态为i的方案（i是采用二进制压缩存储的点集覆盖状态）

// 比较两个浮点数是否相等
int cmp(double x, double y) {
    if (fabs(x - y) < eps) return 0; // 相等
    if (x < y) return -1;
    return 1;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;

		// 处理出path数组
        memset(path, 0, sizeof path);
        for (int i = 0; i < n; i++) {
            // 整个数据只有一个点的时候，这里对只覆盖一个点的抛物线特殊处理：只覆盖自己
            path[i][i] = 1 << i;
            for (int j = 0; j < n; j++) {
                double x1 = q[i].x, y1 = q[i].y;
                double x2 = q[j].x, y2 = q[j].y;
                
                if (!cmp(x1, x2)) // 特判 x1 == x2，此时斜率无穷大
                    continue;
                    
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;

                if (cmp(a, 0) >= 0) continue; // 抛物线必须开口向下
                
                // 枚举哪些点被抛物线覆盖
                for (int k = 0; k < n; k++) 
                {
                    double x = q[k].x, y = q[k].y;
                    if (!cmp(a * x * x + b * x, y)) // 如果在抛物线上
                        path[i][j] += 1<
            int x = 0;
            for (int j = 0; j < n; j++) // 存储从i中找到任意一个没有被覆盖掉的列
                if (!(i >> j & 1)) {
                    x = j;
                    break;
                }

            for (int j = 0; j < n; j++) // 枚举所有能覆盖x的抛物线 path[x][j]
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
        }

        cout << f[(1 << n) - 1] << endl;
    }

    return 0;
}

2.3、宝藏

ACwing 529