[数据结构与算法]【动态规划】状压dp：炮兵阵地

?

?代码：

#include <iostream>
#include <vector>

using namespace std;

const int N = 110, M = 1 << 10;
int n, m;
int g[N], cnt[M];
int f[2][M][M];
vector<int> state;
vector<int> head[M];

bool check(int st)
{
    return !(st & st >> 1 || st & st >> 2);
}
int count(int st)
{
    int res = 0;
    while (st) res += st & 1, st >>= 1;
    return res;
}
int main()
{
    //input
    cin >> n >> m;
    for (int i = 1, j = 0; i <= n; ++ i, j = 0)
        for (char c; j < m && cin >> c; ++ j)   //纯属为了压行,没有其他意思w
            g[i] += (c == 'H') << j;
    //找出所有合法状态
    for (int st = 0; st < 1 << m; ++ st)
        if (check(st))
            state.push_back(st), cnt[st] = count(st);
    //找出所有合法状态的合法转移
    for (int cur_st: state)
        for (int pre_st: state)
            if (!(cur_st & pre_st))
                head[cur_st].push_back(pre_st);
    //dp
    for (int i = 1; i <= n; ++ i)
        for (int st: state)
            if (!(g[i] & st))
                for (int p1: head[st])
                    for (int p2: head[p1])
                        if (!(st & p2))
                            f[i&1][st][p1] = max(f[i&1][st][p1], f[i-1&1][p1][p2] + cnt[st]);
    //Enumerate the final state
    int res = 0;
    for (int st: state)
        for (int pre: head[st])
            res = max(res, f[n&1][st][pre]);
    //output
    cout << res << endl;
    return 0;
}

来源：AcWing

?

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖