二维状压DP经典题

炮兵阵地

题目大意：在n*m的地图上放置炮兵，每个炮兵的攻击范围是上下左右两格内，有两种不同的地形，山地（用“H” 表示），平原（用“P”表示），只有平原可以布置炮兵，在不冲突的前提下最多可以布置多少炮兵？

这道题非常经典，我们用dp[i] [j] [k]表示第i行在第j种选取状态下，第i-1行在第k种选取状态下前i行最多摆放的炮兵数量。然后我们首先预处理每一行所有的合法状态，以降低时间复杂度。用num[i]表示第i行的合法状态数量，state[i] [j]表示第i行的第j种合法状态是什么，用temp[i]存储第i行的初始状态，用c[i]存储每种合法状态对应的炮兵数量。

可以不处理直接枚举所有状态吗

如果不预先处理合法状态，那么每一行所有的状态可能有2^10 = 1024种，由于炮兵的摆放需要考虑前两行的状态，那么三个循环枚举状态就会达到惊人的时间复杂度，所以预处理很关键！进行预处理我们会发现每一行的合法状态最多60种，这样即使是3个循环复杂度也会很低。

其他细节都在代码里了。

#include <bits/stdc++.h>

using namespace std;

int n,m,ans;

int dp[105][65][65];

int num[105],temp[105];

int state[105][65];

int c[1 << 10 + 5];

int count(int x){

    int sum = 0;

    while(x){

        if(x & 1) sum++;

        x >>= 1;

    }

    return sum;

}

int main(){

	cin >> n >> m;

    //每行的合法状态最多只有60种!

    // int p = 0;

    // for(int i = 0;i< (1 << 10);i++){

    //     int now = i;

    //     if((now & (now >> 1)) == 0 && (now & (now >> 2)) == 0) p++;

    // }

    // cout << p << endl;

    for(int i = 1;i <= n;i++){

    	string s;

        cin >> s;

        for(int j = 0;j < m;j++){

            if(s[j] == 'P') temp[i] += (1 << j);

        }

    }

    //对第0行特殊处理

    state[0][++num[0]] = 0;

    //预处理合法状态

    for(int i = 0;i < (1 << m);i++){

        for(int j = 1;j <= n;j++){

            int now = i;

            if(!(now & (now >> 1)) && !(now & (now >> 2))

               && (now | temp[j]) == temp[j]){

                state[j][++num[j]] = i;

                c[i] = count(i);

            }

        }

    }

    for(int i = 1;i <= n;i++){

        for(int j = 1;j <= num[i];j++){

            int now = state[i][j];

            //对第一行特殊处理，防止越界

            if(i == 1) {

                dp[i][j][1] = max(dp[i][j][1],c[now]);

                continue;

            }

            for(int k = 1;k <= num[i - 1];k++){

                int pre = state[i - 1][k];

                if(!(now & pre)){

                    for(int l = 1;l <= num[i - 2];l++){

                        int pree = state[i - 2][l];

                        if(!(now & pree) && !(pre & pree)){

                            dp[i][j][k] = max(dp[i][j][k],dp[i - 1][k][l] + c[now]);

                        }

                    }

                }

            }

        }

    }

    for(int i = 1;i <= num[n];i++){

        for(int j = 1;j <= num[n - 1];j++){

			ans = max(ans,dp[n][i][j]);

        }

    }

    cout << ans << endl;

    return 0;

}

排兵布阵 HDU4539

题目链接

大意：一个n*m的平原布置士兵。每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然，一个士兵不能站在另外一个士兵所能攻击到的位置，同时因为地形的原因也不是每一个位置都可以安排士兵。（输入中1可以布置，0不可以布置）问：最多能安排多少个士兵。

思路和上一题基本一样，换汤不换药.

#include<bits/stdc++.h>

using namespace std;

int n,m,ans;

int state[105],num[170],c[1 << 10 + 5],legal[105][170],dp[105][170][170];

int count1(int x){

    int sum = 0;

    while(x){

        if(x & 1) sum++;

        x >>= 1;

    }

    return sum;

}

bool ok(int now,int row){

    return (now & (now >> 2)) == 0 && (now | state[row]) == state[row];

}

bool check(int now,int pre){

    return (now & (pre >> 1)) == 0 && (now & (pre << 1)) == 0;

}

bool recheck(int now,int pree){

    return (now & pree) == 0;

}

//由于是多组数据，所以每次都要初始化!

void init(){

    ans = 0;

    memset(num,0,sizeof(num));

    memset(dp,0,sizeof(dp));

    memset(state,0,sizeof(state));

}

int main()

{

    memset(c,-1,sizeof(c));

    while(~scanf("%d %d",&n,&m)){

        init();

        for(int i = 1;i <= n;i++){

            for(int j = 0;j < m;j++){

               int x;

               scanf("%d",&x);

               if(x) state[i] |= (1 << j);

            }

        }

        //预处理合法状态

        legal[0][++num[0]] = 0;

        for(int i = 0;i < (1 << m);i++){

            for(int j = 1;j <= n;j++){

                if(ok(i,j)) {

                    legal[j][++num[j]] = i;

                    if(c[i] == -1) c[i] = count1(i);

                }

            }

        }

        for(int i = 1;i <= n;i++){

            for(int j = 1;j <= num[i];j++){

                int s1 = legal[i][j];

                if(i == 1) {

                    dp[i][j][1] = max(dp[i][j][1],c[s1]);

                    continue;

                }

                for(int k = 1;k <= num[i - 1];k++){

                    int s2 = legal[i - 1][k];

                    if(check(s1,s2)){

                        for(int l = 1;l <= num[i - 2];l++){

                            int s3 = legal[i - 2][l];

                            if(recheck(s1,s3)){

                                dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][l] + c[s1]);

                            }

                        }

                    }

                }

            }

        }

        for(int i = 1;i <= num[n];i++){

            for(int j = 1;j <= num[n - 1];j++){

                ans = max(ans,dp[n][i][j]);

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

二维状压DP经典题

炮兵阵地

排兵布阵 HDU4539

最新文章

热门文章