Poj 1185 炮兵阵地 (DP_状态DP)

解题思路：经典NOI题，矩阵里的状态压缩问题。因为m<=10，而每列都有状态选或不选，所以想到用2进制，那么状态数是2^10。因为当前行的选择依赖于前两行，而前一行又依赖于前前两行，能想到状态转移方程应该牵扯到当前行、前一行、前前行，类似于递推式dp[i] = dp[i-1] + dp[i-2]的递推过程，而本体每次都是状态间的转移，想到状态转移方程dp[i][j][k] = max(dp[i][k][l]) + sum[j](j和k和l表示当前行状态，前一行状态，前前行状态,sum[j]表示j状态下在i行放了几个大炮)。

用上面的转移方程，空间复杂度和时间复杂度都不允许，因为j,k,l<=2^10,而实际的情况是10列的组合中不冲突的组合只有少数几种，比如PHPP，状态5（101）表示的在第0列和第2列放炮，这个状态内部冲突，我们就可以不考虑，可以预处理把这些状态剔除，然后将不冲突的状态存进一个数组，转移的时候用数组的下标去转移就好。状态转移方程变成:dp[i][j][k] = max(dp[i][k][l]) + one[i][j](j,k,l分别表示第i行，第i-1行，第i-2行的第j个、第k个，第l个状态，状态分别为state[i][j],state[i-1][k],state[i-2][l]，one[i][j]表示第i行状态j的1的个数，也就是i状态下放炮数量),最坏复杂度O(N*K^3)（K<62)

推荐几篇好的解题报告：http://apps.hi.baidu.com/share/detail/14572384

http://www.cppblog.com/infinity/archive/2009/05/20/62325.html

测试数据：

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

代码：

#include <stdio.h>
#include <string.h>
#define MAX 110
#define INF 1000000000


int state[MAX][MAX], one[MAX][MAX];         //state[i][j]表示第i行第j个合法状态，one表示第i行第j个合法状态中含1的个数
int ans, stnum[MAX], sum[MAX * 20];         //stnum[i]表示i行合法的状态数，sum[i]为i状态下1的个数
int n, m, map[MAX][MAX], dp[MAX][70][70];   //dp[i][j][k]表示第i行第j个状态第-1行第k个状态含有的最多1的个数


inline int max(int a, int b) {

    return a > b ? a : b;
}
void Initial() {

    ans = 0;
    memset(dp, 0, sizeof (dp));
    memset(map, 0, sizeof (map));
    memset(one, 0, sizeof (one));
    memset(stnum, 0, sizeof (stnum));
}
void GetOneSum() {
    //预处理，先把每个状态里含有的1的数量算出来
    for (int i = 0; i <= (1 << 10); ++i) {

        int tp = 0;
        for (int j = 0; j <= 10; ++j)
            if (i & (1 << j)) tp++;
        sum[i] = tp;
    }
}
int Check(int x) {
    //x&(x>>1)是判断当前列是否和前一列冲突,x>>2就是前两列
    if (x > 1 && (x & (x >> 1))) return 0;
    if (x > 2 && (x & (x >> 2))) return 0;
    return 1;
}
void FindState(int x, int tot) {
    //预处理，把第x行中合法的状态全部找出来，存到state数组中，tot是本行所有的p点压缩起来的一个状态
    for (int i = 0; i < (1 << m); ++i)
        if (Check(i) && (i & tot) == i) {
            //（i&tot） == i表示集合i是集合tot的子集合，意思是i里面的含有的列都是p点
            stnum[x]++;
            int tp = stnum[x];
            state[x][tp] = i;
            one[x][tp] = sum[i];
        }
}


int main() 
{
    int i, j, k, s;
    char tp[MAX];
    GetOneSum();


    while (scanf("%d%d", &n, &m) != EOF) {

        Initial(), stnum[0] = 70;
        for (i = 1; i <= n; ++i) {

            scanf("%s", tp);
            for (k = j = 0; j < m; ++j) {
             
                map[i][j] = (tp[j] == 'P' ? 1 : 0);
                k += (map[i][j] ? (1 << j) : 0);
            }
            FindState(i, k);
        }


        //初始化第1行
        for (j = 1; j <= stnum[1]; ++j)
            for (k = 1; k <= stnum[0]; ++k)
                dp[1][j][k] = one[1][j];
        //状态转移
        for (i = 2; i <= n; ++i)
            for (j = 1; j <= stnum[i]; ++j)
                for (k = 1; k <= stnum[i - 1]; ++k)
                    if (!(state[i][j] & state[i - 1][k])) {                 //判断两个状态是否有冲突

                        int tpmax = 0;
                        for (s = 0; s <= stnum[i - 2]; ++s) {

                            if (!(state[i][j] & state[i-2][s])              //判断三个状态是否有冲突
                                    && !(state[i - 1][k] & state[i - 2][s]))
                                tpmax = max(dp[i - 1][k][s], tpmax);
                        }
                        dp[i][j][k] = tpmax + one[i][j];
                    }

        //Update Answer
        for (j = 1; j <= stnum[n]; ++j)
            for (k = 1; k <= stnum[n-1]; ++k)
                ans = max(ans, dp[n][j][k]);
        printf("%d\n", ans);
    }
}

本文ZeroClock原创，但可以转载，因为我们是兄弟。

分享到：