首页 > 代码库 > poj1185炮兵阵地状压dp

poj1185炮兵阵地状压dp

2024-07-17 08:27:09   218人阅读

　　压前两行的状态很容易想到，但是 直接搞  (1<<10) * (1<<10)  空间时间都明显受不了， 但是经过高人指点，你会发现：枚举每一行可行的状态，其实并不多，预先打表处理，不用 1->(1<<10)枚举每一种状态。。

然后记忆化搜就ok了。

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int deal(int a,int b){    return (a&(1<<b));}int m,n;int chart[1000];int vis[111];int len;int Map[111];int dp[111][222][222];int Max(int a,int b){    return a>b? a:b;}int Min(int a,int b){    return a>b?b:a;}int judge(int x){    for(int i=0;i<m;i++)if(deal(x,i)){        int t= Max(0,i-2);int t1=Min(m-1,i+2);        for(int j=t;j<=t1;j++){        if(i==j) continue;        if(deal(x,j)) return 0;        }    }    return 1;}void Init(){    int gg=1<<m;    for(int i=0;i<gg;i++){        if(judge(i))chart[len++]=i;    }}int panduan(int x,int yici,int erci,int mat){    if(yici&x) return 0;    if(erci&x) return 0;    if(x&(~mat)) return 0;   // for(int i=0;i<m;i++) if(deal(x,i)) if(!deal(mat,i)) return 0;    return 1;}int gao(int x,int yici,int erci){    if(~dp[x][yici][erci]) return dp[x][yici][erci];    if(x==n) return dp[x][yici][erci]= 0;    int ret=0;    for(int i=0;i<len;i++){        if(panduan(chart[i],chart[yici],chart[erci],Map[x])) ret=Max(ret,gao(x+1,i,yici)+vis[i]);    }    return dp[x][yici][erci]= ret;}void Init1(){    memset(vis,0,sizeof(vis));    for(int i=0;i<len;i++){        int tem=chart[i];int ans=0;        for(int j=0;j<m;j++){            if(tem&1) ans++;            tem>>=1;        }        vis[i]=ans;    }}int main(){    char str[1000];    while(cin>>n>>m){        len=0;        Init();Init1();        memset(dp,-1,sizeof(dp));        memset(Map,0,sizeof(Map));        for(int i=0;i<n;i++){            scanf("%s",str);            for(int j=0;j<m;j++){                if(str[j]==‘P‘)Map[i]|=(1<<j);            }        };        cout<<gao(0,0,0)<<endl;    }    return 0;}

 


联系
我们