状态压缩动态规划——布阵类问题

这三道题目异曲同工，如果不能完成，那么看懂一道题的题解后，自己实现剩余两道应该没有问题

顺便附一个状压dp的视频讲解
点此进入
POJ-3254 Corn Fields

#include<cstdio>
#include<algorithm>
#include<cstring>

const int MOD=100000000,STATE=1<<12,ROW=12+1;

int St[STATE+1],Bare[ROW],dp[ROW][STATE];

int main(){
    int k=0;
    for(int i=0;i<STATE;++i)if(!(i&(i<<1)))St[k++]=i;//每行所有的合法状态
    St[k]=STATE;
    int m,n,t;
    scanf("%d%d",&m,&n);
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j){
            scanf("%d",&t);Bare[i]=(Bare[i]<<1)|(!t);
        }
    }
    int s=1<<n;
    for(int i=0;St[i]<s;++i)if(!(Bare[0]&St[i]))dp[0][i]=1;
    for(int r=1;r<m;++r){
        for(int i=0;St[i]<s;++i){
            if(!(Bare[r-1]&St[i])){
                for(int ri=0;St[ri]<s;++ri){
                    if(!(Bare[r]&St[ri]) && !(St[i]&St[ri])){
                        dp[r][ri]=(dp[r][ri]+dp[r-1][i])%MOD;
                    }
                }
            }
        }
    }
    int ans=dp[m-1][0];
    for(int i=1;St[i]<s;++i){
        ans=(ans+dp[m-1][i])%MOD;
    }
    printf("%d\n",ans);
    return 0;
}

HDU-4539 排兵布阵

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>

const int STATE=1<<10;
int dp[101][180][180],num[1<<10+1],St[201],marsh[201];

int get_bit1(int x){
    int nx=0;
    while(x){
        if(x%2)nx++;
        x/=2;
    }
    return nx;
}

bool ok(int x,int y){
    if(x & y<<1 || x<<1 & y) return 0; 
    return 1;
}

int main(){
    int m,n,k=0;
    for(int i=0;i<STATE;++i){
        if(!(i&(i<<2)))St[k++]=i;
        num[i]=get_bit1(i);
    }
    St[k]=STATE;
    //std::cout<<k<<"\n";
    while(scanf("%d%d",&n,&m)==2&&n){
        memset(dp,-1,sizeof(dp));
        int t;
        for(int i=0;i<n;++i){
            marsh[i]=0;
            for(int j=0;j<m;++j){
                scanf("%d",&t);marsh[i]=(marsh[i]<<1)|(!t);
            }
        }
        int s=1<<m;
        for(int i=0;St[i]<s;++i){
            if(!(marsh[0]&St[i]))
            for(int j=0;St[j]<s;++j){
                dp[0][i][j]=num[St[i]];
            }
        }

        for(int i=0;St[i]<s;++i){
            if(!(marsh[1]&St[i]))
            for(int j=0;St[j]<s;++j){
                if(ok(St[i],St[j]) && !(marsh[0]&St[j]))
                for(int kk=0;St[kk]<s;++kk){
                    if(dp[0][j][kk]!=-1)dp[1][i][j]=std::max(dp[0][j][kk]+num[St[i]],dp[1][i][j]); 
                }

            }
        }

        for(int r=2;r<n;++r){
            for(int i=0;St[i]<s;++i){
                if(!(St[i]&marsh[r-2])){
                    for(int ri1=0;St[ri1]<s;++ri1){
                        if(!(St[ri1]&marsh[r-1])){
                            for(int ri=0;St[ri]<s;++ri){
                                if(!(St[ri]&marsh[r]) && (!(St[i]&St[ri])) && ok(St[ri1],St[ri]) ){
                                    if(dp[r-1][ri1][i]!=-1)
                                    dp[r][ri][ri1]=std::max(dp[r][ri][ri1],dp[r-1][ri1][i]+num[St[ri]]);
                                }
                            }
                        }
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;St[i]<s;++i)
        {
            for(int j=0;St[j]<s;++j)
            ans = std::max(ans,dp[n-1][i][j]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

POJ-1185 炮兵布阵

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int STATE=1<<11,ROW=101;

inline int get_bit1(int x){
    int nx=0;
    while(x){
        if(x%2)nx++;
        x/=2;
    }
    return nx;
}

int st[101],n,m,marsh[101],dp[ROW][101][101],ST,num[STATE];
char tab[ROW][10+1];

inline void init(){
    for(int i=0;i<n;++i){
        marsh[i]=0;
        for(int j=0;j<m;++j)
            if(tab[i][j]!='P')marsh[i]=(marsh[i]<<1)|1;
            else marsh[i]=marsh[i]<<1;
    }
    memset(dp,-1,sizeof(dp));
    ST=1<<m;
    for(int i=0;st[i]<ST;++i){
        if(!(marsh[0]&st[i]))
        for(int j=0;st[j]<ST;++j){
            dp[0][i][j]=num[st[i]];
        }
    }
}

int dfs(int row,int r1,int r2){
    int &d=dp[row][r1][r2];
    if(row==0||d!=-1){
        return d;
    }
    d=0;
    if(row==1){
        for(int r3=0;st[r3]<ST;++r3){
            if(!(st[r1]&st[r2]) && dp[row-1][r2][r3]!=-1 &&!(marsh[row]&st[r1])){
                d=std::max(d,dfs(row-1,r2,r3)+num[st[r1]]);
            }
        }
        return d;
    }

    if(!(marsh[row-1]&st[r2]) && !(marsh[row]&st[r1])){
        for(int r3=0;st[r3]<ST;++r3){
            if(!(marsh[row-2]&st[r3])){
                if(!(st[r1]&st[r2]) && !(st[r2]&st[r3]) && !(st[r1]&st[r3])){
                    d=std::max(d,dfs(row-1,r2,r3)+num[st[r1]]);
                }
            }
        }
    }
    return d;
}
int main(){
    int k=0;
    for(int i=0;i<STATE;++i){
        if(!((i<<2)&i) && !((i<<1)&i))st[k++]=i;
        num[i]=get_bit1(i);
    }st[k]=STATE;
    while(scanf("%d%d",&n,&m)==2&&n){
        for(int i=0;i<n;++i)scanf("%s",tab[i]);
        init();
        int ans=0;
        for(int i=0;st[i]<ST;++i){
            for(int j=0;st[j]<ST;++j){
                ans=std::max(ans,dfs(n-1,i,j));
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}