Menu
Article ACM

状压DP 再入门 ！！！

NodeKey

NodeKey

• 6 min read

昨天写状压DP被煞笔天海和死肥宅带鱼嘲笑了

Damn！

然而事实也是一些状压DP的经典问题我还不会……
更烦人的是今天的多校是DP专场，AC自动机+DP 这个倒是常见的套路 树形DP ，反背包DP，树上匹配+DP，各种姿势的DP……

老实说，我的DP是很弱的……连背包问题上的我个人觉得都不是很熟练……

这里写一下状压DP入门的三道题，三道题其实差不了多少，但在难度上基本上是循序渐进的。

POJ 3254 Corn Fields

题意：
给你一个矩阵，让你种一些玉米，要求只能在给定的格子上种，并且相邻的格子不能同时存在玉米。
问方案数。

思路：
首先在输入的时候记录一下每一行不可种植的格子，将它压缩为二进制。
再是筛选出在同一行满足条件的所有状态，因为不能存在相邻格子，也就是 ( i & ( i << 1 ) = 0 )

枚举每一行满足条件的所有状态，进而枚举下一行满足条件的所有状态，当 ( state[i] & state[j] ==0 )时，就表示上下状态的玉米不会相邻，这两行是满足题意的，所以只要将当前状态的数量加到下一行的状态中。

最后将最后一行的所有状态数相加即为我们要求的答案。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 20;
const int maxm = 5000;
const int mod = 1e8;

int dp[maxn][maxm];
int val[maxn], state[maxm];

int main()
{
    int n, m, top, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        fill(dp, 0), fill(val, 0), top = 0;
        each(i, n) each(j, m)
        {
            scanf("%d", &v);
            v ? 0 : val[i] += (1 << (m - j - 1));
        }
        each(i, (1 << m)) if (!(i & (i << 1))) state[top++] = i;
        each(i, top) if (!(state[i] & val[0])) dp[0][i] = 1;
        range(i, 1, n - 1) each(j, top)
        {
            if (state[j] & val[i])
                continue;
            each(k, top)
            {
                if (state[k] & val[i - 1])
                    continue;
                if (state[j] & state[k])
                    continue;
                dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
            }
        }
        range(i, 1, top - 1) dp[n-1][0] = (dp[n-1][0] + dp[n-1][i]) % mod;
        printf("%d\n", dp[n-1][0]);
    }
    return 0;
}

POJ 1185 炮兵阵地

题意：
题意基本和上一题一致，不过不能同时放置的范围从一个长度为 ( 1 ) 的 十字，增大 到长度为 ( 2 ) 的十字。

问能放置的最大数量。

思路：
思路基本一致，不过存储状态数几何倍上升，需要记录两行的状态，用当前的两行去枚举判断下面的两行。判断一下可行性后，将两个状态的数量比较一下即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 110;
const int maxm = 70;
const int mod = 1e8;

int dp[maxn][maxm][maxm];
int val[maxn], state[maxm], soldier[maxm];
int n, m, top, v;

char buf[15];

int main()
{
    scanf("%d %d", &n, &m);
    each(i, n)
    {
        scanf("%s", buf);
        each(j, m) if (buf[j] == 'H') val[i] += (1 << (m-j-1) );
    }
    each(i, (1 << m)) if ((i & (i << 1) || (i & (i << 2)))) continue;
    else soldier[top] = __builtin_popcount(i), state[top++] = i;
    each(i, top) if (!(state[i] & val[0])) dp[0][i][0] = soldier[i];
    each(i, top) if (!(state[i] & val[1]))
    {
        each(j, top) if (!(state[j] & val[0]) && !(state[i] & state[j]))
        {
            dp[1][i][j] = max(dp[1][i][j], dp[0][j][0] + soldier[i]);
        }
    }
    range(r, 2, n - 1) each(i, top) if (!(state[i] & val[r]))
    {
        each(j, top) if (!(state[j] & val[r - 1]) && !(state[i] & state[j]))
        {
            each(k, top) if (!(state[k] & val[r - 2]) && !(state[j] & state[k]) && !(state[i] & state[k]))
            {
                dp[r][i][j] = max(dp[r][i][j], dp[r - 1][j][k] + soldier[i]);
            }
        }
    }
    int ans = 0;
    each(i, top) each(j, top) ans = max(ans, dp[n - 1][i][j]);
    printf("%d\n", ans);
    return 0;
}

HDU 4539 郑厂长系列故事——排兵布阵

题意：
这道题和上一题几乎如出一辙，只是同时放置的范围再次改变了……
从一个大十字变成了 曼哈顿距离不超过 ( 2 )的范围。

注： 两点 ( \left( x_0, y_0 \right) ) 与 ( \left( x_1 , y_1 \right) ) 曼哈顿距离 为 ( \left| x_0 – x_1 \right| + \left| y_0 – y_1 \right| )

思路：
一个思路，只是判断可行性的时候有点不一样罢了……

比较建议上一题学着敲，这道自己敲。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 110;
const int maxm = 205;

int dp[maxn][maxm][maxm];
int val[maxn], state[maxm], soldier[maxm];
int top, v, row, col;

bool check(int a, int b) { return (a & (b << 1)) == 0 && (a & (b >> 1)) == 0; }

int main()
{
    while (scanf("%d %d", &row, &col) != EOF) {
        if (row == 0 || col == 0) {
            puts("0");
            continue;
        }
        fill(dp, 0), fill(val, 0), top = 0;
        each(i, row) each(j, col)
        {
            scanf("%d", &v);
            v ? 0 : val[i] += 1 << (col - j - 1);
        }
        each(i, (1 << col)) if (!(i & (i << 2))) soldier[top] = __builtin_popcount(i), state[top++] = i;
        each(i, top) if (!(state[i] & val[0])) dp[0][i][0] = soldier[i];
        each(i, top) if (!(state[i] & val[1]))
        {
            each(j, top) if (!(state[j] & val[0]) && check(state[i], state[j]))
            {
                dp[1][i][j] = max(dp[1][i][j], dp[0][j][0] + soldier[i]);
            }
        }
        range(r, 2, row - 1) each(i, top) if (!(state[i] & val[r]))
        {
            each(j, top) if (!(state[j] & val[r - 1]) && check(state[i], state[j]))
            {
                each(k, top) if (!(state[k] & val[r - 2]) && check(state[k], state[j]) && (state[k] & state[i]) == 0)
                {
                    dp[r][i][j] = max(dp[r][i][j], dp[r - 1][j][k] + soldier[i]);
                }
            }
        }
        int ans = 0;
        each(i, top) each(j, top) ans = max(ans, dp[row - 1][i][j]);
        printf("%d\n", ans);
    }
    return 0;
}
Share