acwing算法提高之动态规划--状态压缩DP

1 基础知识

暂无。。。

2 模板

暂无。。。

3 工程化

题目1：小国王。

解题思路：状态压缩DP。

状态定义f[i][j][a]：表示已经考虑了前i行，并且摆放了j个国王，且第i行的状态是a的总方案数。

定义第i行的合理状态a：二进制表示中没有连续的两个1。与第i-1行不冲突，比如第i-1行的状态是b，那么需要满足a & b == 0和a | b没有连续的两个1。

状态转移，先计算出所有合法的状态，存储在向量states中，然后预先处理出每个状态a可以从状态b转移过来unordered_map<int, vector<int>> g。

C++代码如下，

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

const int N = 12, M = 1 << N;
int n, m;
long long f[N][N*N][M];
vector<int> states; //合法的状态
unordered_map<int,vector<int>> g;

bool check(int x) {
    //是否存在连续的两个1
    for (int i = 0; i < 31; ++i) {
        if ((x >> i & 1) && (x >> (i + 1) & 1)) {
            return false; //非法的状态
        }    
    }
    return true;
}

int get_cnt(int x) {
    //二进制中1的个数
    int res = 0;
    for (int i = 0; i < 31; ++i) {
        if (x >> i & 1) res += 1;
    }
    return res;
}

int main() {
    cin >> n >> m;
    
    for (int i = 0; i < 1 << n; ++i) {
        if (check(i)) {
            states.emplace_back(i);
        }
    }
    
    for (auto a : states) {
        for (auto b : states) {
            if ((a & b) == 0 && check(a | b)) {
                g[a].emplace_back(b);
            }
        }
    }
    
    //初始化状态
    f[0][0][0] = 1;
    for (int i = 1; i <= n + 1; ++i) {
        for (int j = 0; j <= m; ++j) {
            for (auto a : states) {
                for (auto b : g[a]) {
                    int cnt = get_cnt(a);
                    if (j >= cnt) {
                        f[i][j][a] += f[i-1][j-cnt][b];
                    }
                }
            }
        }
    }
    
    cout << f[n+1][m][0] << endl;

    return 0;   
}

题目2：玉米田。

状态定义f[i][a]：考虑前i行，且第i行的状态是a的所有方案数。

第i行的状态a需要满足：二进制表示中没有两个相邻的1。与第i-1行的状态b不冲突，即(a & b) == 0。只能在肥沃的土地种玉米。

可以预处理出合法的状态，存储在向量states中，然后考虑每一行的肥沃土地，可以换一种思路，将贫瘠的土地构成的状态记为row[i]，则需要满足(a & row[i]) == 0。

C++代码如下，

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

const int N = 15, M = 1 << N, mod = 1e8;
int n, m;
vector<int> row; //表示不育
vector<int> states;
unordered_map<int, vector<int>> g; //状态a可以由状态b转移过来
int f[N][M];

bool check(int x) {
    for (int i = 0; i < 31; ++i) {
        if ((x >> i & 1) && (x >> (i + 1) & 1)) {
            return false; //非法状态
        }
    }
    return true; //合法状态
}

int main() {
    cin >> n >> m; //n行m列
    
    row.emplace_back(0);
    for (int i = 0; i < n; ++i) {
        int t = 0;
        for (int j = 0; j < m; ++j) {
            int x;
            cin >> x;
            if (x == 0) {
                t += 1 << j;
            }
        }
        row.emplace_back(t);//不育
    }
    
    
    for (int i = 0; i < 1 << m; ++i) {
        if (check(i)) {
            states.emplace_back(i);
        }
    }
    
    for (auto a : states) {
        for (auto b : states) {
            if ((a & b) == 0) {
                g[a].emplace_back(b);
            }
        }   
    }
    
    //状态计算
    f[0][0] = 1;
    for (int i = 1; i <= n + 1; ++i) {
        for (auto a : states) {
            if (a & row[i]) continue;
            for (auto b : g[a]) {
                if (b & row[i-1]) continue;
                if ((a & b) == 0) {
                    f[i][a] = (f[i][a] + (f[i-1][b] % mod)) % mod;
                }
            }
        }
    }
    
    cout << f[n+1][0] << endl;
    
    return 0;
}

题目3：炮兵阵地。

解题思路：状态压缩DP。由于空间有限，所以需要用到滚动数组，在原地址上更新滚动数组，暂时没有理解到本质，先空着。

状态定义f[i][a][b]：考虑前i行，且第i-1行的状态是a，第i行的状态是b，该case下的最大摆放炮兵的数目。

合法状态：两个1之间至少空了2个位置。第i行、第i-1行和第i-2行任意两个不能互相攻击到，记第i-1行的状态为a，第i行的状态为b，第i-2行的状态为c，那么有((a & b) | (a & c) | (b & c)) == 0。

同时，还有一个额外需要考虑的，就是山顶不能放置炮兵，记第i行山顶的状态为row[i]，那么需要满足(b & row[i]) == 0。

C++代码如下，

#include <iostream>
#include <vector>
#include <cstring>
#include <unordered_map>

using namespace std;

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

int n, m;
vector<int> states;
vector<int> row(N, 0);
int f[2][M][M];

bool check(int x) {
    for (int i = 0; i < 31; ++i) {
        if ((x >> i & 1) && ((x >> (i + 1) & 1) || (x >> (i + 2) & 1))) {
            return false; //非法状态
        }
    }
    return true;
}

int get_count(int x) {
    int res = 0;
    for (int i = 0; i < 31; ++i) {
        if (x >> i & 1) res += 1;
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int t = 0;
        for (int j = 0; j < m; ++j) {
            char c;
            cin >> c;
            if (c == 'H') {
                t += 1 << j;
            }
        }
        row[i] = t;
    }
    
    //处理合理状态
    for (int i = 0; i < 1 << m; ++i) {
        if (check(i)) {
            states.emplace_back(i);
        }
    }
    
    //计算状态
    for (int i = 1; i <= n; ++i) {
        for (auto a : states) {//第i-1行的状态是a
            for (auto b : states) { //第i行的状态是b
                for (auto c : states) {//第i-2行的状态是c
                    if ((a & row[i-1]) || (b & row[i])) continue; //山上不能放置炮兵
                    if ((a & b) || (a & c) || (b & c)) continue; //行与行之间不能攻击到
                    f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][c][a] + get_count(b));
                }
            }
        }
    }
    
    int res = 0;
    for (auto a : states) {
        for (auto b : states) {
            res = max(res, f[n & 1][a][b]);
        }
    }
    cout << res << endl;
    
    return 0;
}

题目4：愤怒的小鸟。

解题思路：没有看懂，有时间再推敲。

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 18, M = 1 << N;
const double eps = 1e-8;

int n, m;
PDD q[N];
int path[N][N];
int f[M];

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;
        
        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)) continue;
                
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;
                
                if (cmp(a, 0) >= 0) continue;
                int state = 0;
                for (int k = 0; k < n; ++k) {
                    double x = q[k].x, y = q[k].y;
                    if (!cmp(a * x * x + b * x, y)) state += 1 << k;
                }
                path[i][j] = state;
            }
        }
        
        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        for (int i = 0; i + 1 < 1 << n; ++i) {
            int x = 0;
            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;
    }
    
    return 0;
}