《算法竞赛进阶指南》0x56状态压缩DP POJ1185

给定一个n*m的矩阵，每个点可能是山也可能是平地，在上面放士兵，只能放在平地上，每个点上下左右两格为攻击范围，士兵之间的攻击范围不能覆盖中心点，问最多可以放多少个士兵。

解决方案：一行的状态由前面两行决定，如果用01表示不放和放的话，那么状态就是前i行，第i-1行状态是j，第i行的状态是k，第i阶段只和第i-1阶段的有关系

可以处理出行内的合法状态，并保存在集合S中，三行之间放的应该没有交集，并且第i行不能放在山上，所以要判断，然后枚举三行的状态即可。

最后对第n层的情况下进行枚举，或者计算到n+2层，并且n+2层和n+1层的都是0，表示最后两层都不放，前n+2层能放的最大的数量。

代码；

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N = 110,M=10,S=1<<M;
int f[2][S][S];
int n,m;
int g[N];
vector<int> state;
int cnt[S];//状态中1的数量 
bool check(int s){
    for(int i=0;i<m;i++)//为1的一位后面两位都要是0才正确 
        if((s>>i & 1) && ((s>>i+1 & 1) || (s>>i+2 & 1)))
            return false;
    return true;
}
int count(int s){
    int cnt=0;
    while(s){
        cnt+=s&1;
        s>>=1;
    }
    return cnt;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++){
            char c;
            cin>>c;
            if(c=='H')g[i]+=1<<j;
        }
    
    for(int i=0;i<1<<m;i++){
        if(check(i)){//查看i状态是否满足行内1之间距离大于等于2 
            state.push_back(i);
            cnt[i]=count(i); 
        }
    }
    
    f[1][0][0]=0; 
    for(int i=1;i<=n;i++){
        for(int j=0;j<state.size();j++)
            for(int k=0;k<state.size();k++)
                for(int u=0;u<state.size();u++){
                    int a=state[u],b=state[j],c=state[k];
                    if((a&b) || (a&c) || (b&c))continue;//状态存在交集 
                    if(c & g[i])continue;//第i行没放在山上 
                    f[i & 1][j][k]=max(f[i & 1][j][k],f[i-1 & 1][u][j]+cnt[c]); 
                }
    }
    int ans=-0x3f3f3f3f;
    for(int i=0;i<state.size();i++)
        for(int j=0;j<state.size();j++){
            if(!(state[i] & state[j]))
                ans=max(ans,f[n & 1][i][j]);
        }
        
    cout<<ans<<endl;
}

《算法竞赛进阶指南》0x56状态压缩DP POJ1185

相关推荐