首页 > 代码库 > POJ 1185 状压DP

POJ 1185 状压DP

2024-07-29 20:24:04   230人阅读

legal[] 保存所有在当前行可显示的状态，由dfs得到，len[]保存legal[]对应下标状态中的 1 的个数 ， 也就是放置炮台的个数

state[i] 表示第 i 行这块区域的土地情况，H表示 1 ，P表示 0

那么每次加入一个legal状态  都要符合 !(legal[i] & state[k])

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 int dp[105][80][80],vis[12],state[105],legal[80],len[80]; 6 int cnt,n,m; 7  8 void dfs(int u , int _state , int l) 9 {10     if(u > m){11         legal[++cnt] = _state;12         len[cnt] = l;13         return;14     }15     int flag = 1;16     if(u>1){17         if(vis[u-1]) flag=0;18     }19     if(u>2){20        if(vis[u-2]) flag=0;21     }22     if(flag){23         vis[u] = 1;24         dfs(u+1 , _state<<1|1 , l+1);25         vis[u] = 0;26     }27     dfs(u+1 , _state<<1 , l);28 }29 30 void DP()31 {32     for(int k=1;k<=n;k++){33         for(int i=1;i<=cnt;i++){34             for(int j=1;j<=cnt;j++){35                 if(k == 1 && !(state[k] & legal[i])){36                     dp[k][j][i] = len[i];37                 }38                 for(int t=1;t<=cnt;t39                 ++){40                     if(!(state[k] & legal[i]) && !(legal[i] & legal[j]) && !(legal[i] & legal[t]) && !(legal[t] & legal[j])){41                         dp[k][j][i] = max(dp[k][j][i] , dp[k-1][t][j] + len[i]);42                     }43                 }44             }45         }46     }47 }48 49 int main()50 {51     //freopen("POJ1185.test","rb",stdin);52     char c;53     while(~scanf("%d%d",&n,&m)){54         for(int i=1;i<=n;i++){55             state[i] = 0;56             for(int j=1 ; j<=m ; j++){57                 cin>>c;58                 if(c == ‘H‘) state[i] = state[i]<<1|1;59                 else state[i] = state[i]<<1;60             }61         }62         cnt=0;63         memset(vis,0,sizeof(vis));64         dfs(1,0,0);65 66         memset(dp,0,sizeof(dp));67         DP();68 69         int ans=0;70         for(int i=1;i<=cnt;i++){71             for(int j=1;j<=cnt;j++){72                 ans = max(dp[n][i][j] , ans);73             }74         }75         cout<<ans<<endl;76     }77 78     return 0;79 }

 

POJ 1185 状压DP


联系
我们