思路：和上一篇思路一樣，但是這里要求最大能排幾個，這里要開三維，記錄上次和上上次的狀態，再一一判定，狀態轉移方程為 dp[i][j][k] = max(dp[i][j][k],dp[i - 1][k][t] + num[j])

代碼：

#include<cstdio> #include<map> #include<set> #include<queue> #include<cstring> #include<string> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long const int N = 500+5; const int MOD = 100000000; const int INF = 0x3f3f3f3f; using namespace std; int n,m,top; int cur[110],state[110],dp[110][110][110],num[110]; void init(){top = 0;int tot = 1 << m;for(int i = 0;i < tot;i++){if(i&(i<<1) || i&(i<<2)) continue;state[++top] = i;for(int j = 0;j < m;j++){if(i&1<<j) num[top]++;}} } int main(){char s[12];scanf("%d%d",&n,&m);memset(dp,0,sizeof(dp));memset(num,0,sizeof(num));memset(cur,0,sizeof(cur));memset(state,0,sizeof(state));init();for(int i = 1;i <= n;i++){scanf("%s",s + 1);cur[i] = 0;for(int j = 1;j <= m;j++){if(s[j] == 'H'){cur[i] |= 1<<(j - 1);}}}for(int i = 1;i <= top;i++){if(cur[1]&state[i]) continue;dp[1][i][1] = num[i];}for(int i = 1;i <= top;i++){if(cur[2]&state[i]) continue;for(int j = 1;j <= top;j++){if(cur[1]&state[j]) continue;if(state[i]&state[j]) continue;for(int k = 1;k <= top;k++){dp[2][i][j] = max(dp[2][i][j],dp[1][j][k] + num[i]);}}}for(int i = 3;i <= n;i++){for(int j = 1;j <= top;j++){if(cur[i]&state[j]) continue;for(int k = 1;k <= top;k++){if(cur[i - 1]&state[k]) continue;if(state[j]&state[k]) continue;for(int t = 1;t <= top;t++){if(cur[i - 2]&state[t]) continue;if(state[k]&state[t]) continue;if(state[j]&state[t]) continue;dp[i][j][k] = max(dp[i][j][k],dp[i - 1][k][t] + num[j]);}}}}ll ans = 0;for(int i = 1;i <= top;i++){for(int j = 1;j <= top;j++){if(dp[n][i][j] > ans) ans = dp[n][i][j];}}printf("%lld\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/KirinSB/p/9408767.html

總結

以上是生活随笔為你收集整理的POJ 1185 炮兵阵地（状压DP）题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。