一道非常典型的狀態壓縮題，對于熟練者來說，絕對算是個水題，但是對于狀態壓縮入門者，這算是一個好題，能讓我們對狀態壓縮有深刻理解。

解題：

1.先找出一行的符合狀態，進行01轉換。

2.因為是和前2行有關的所以建立一個三位數組dp[i][j][k] 表示第i行 第j個狀態 前一個狀態是為k的 最大的炮兵數。

? ? ? ? ? 狀態轉移方程dp[i][j][k]=max(dp[i][j][k],(num[j]+dp[i-1][k][t]));

3.預先處理第一第二行的狀態，方便處理。

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int m,n; int dp[105][100][100],cur[105],state[105],num[105]; int top; int max(int a,int b) {return a>b?a:b; } int num1_number(int a) {int count=0;while(a){if(a%2!=0) count++;a=a/2;}return count; } void Init() {int total=1<<n;for(int i=0;i<total;i++){if(i&(i<<1)) continue;if(i&(i<<2)) continue;state[top]=i;num[top++]=num1_number(i);} } bool fit(int a,int b) {if(a&b) return false;return true; } void DP() {int i,j,k,t;for(i=0;i<top;i++){if(fit(state[i],cur[1]))dp[1][i][0]=num[i];}for(i=0;i<top;i++){if(fit(state[i],cur[2])){for(j=0;j<top;j++){if(!fit(cur[1],state[j])) continue;if(fit(state[j],state[i]))dp[2][i][j]=max(dp[2][i][j],dp[1][j][0]+num[i]);}}}for(i=3;i<=m;i++){for(j=0;j<top;j++){if(!fit(cur[i],state[j])) continue;for(k=0;k<top;k++){if(!fit(cur[i-1],state[k])) continue;if(fit(state[k],state[j]))for(t=0;t<top;t++){if(!fit(cur[i-2],state[t])) continue;if(fit(state[t],state[j])&&fit(state[t],state[k]))dp[i][j][k]=max(dp[i][j][k],(num[j]+dp[i-1][k][t]));}}}}int ans=0;for(i=1;i<=m;i++)for(j=0;j<top;j++)for(k=0;k<top;k++)ans=max(ans,dp[i][j][k]);printf("%d\n",ans); } int main() {int i,j;char s;scanf("%d%d",&m,&n);getchar();memset(num,0,sizeof(num));for(i=1;i<=m;i++){for(j=1;j<=n;j++){s=getchar();if(s=='H') cur[i]+=1<<(n-j);else num[i]++;}getchar();}top=0;Init();DP(); }

總結

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

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