Description

司令部的將軍們打算在NM的網格地圖上部署他們的炮兵部隊。一個NM的地圖由N行M列組成，地圖的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下圖。在每一格平原地形上最多可以布置一支炮兵部隊（山地上不能夠部署炮兵部隊）；一支炮兵部隊在地圖上的攻擊范圍如圖中黑色區域所示：

如果在地圖中的灰色所標識的平原上部署一支炮兵部隊，則圖中的黑色的網格表示它能夠攻擊到的區域：沿橫向左右各兩格，沿縱向上下各兩格。圖上其它白色網格均攻擊不到。從圖上可見炮兵的攻擊范圍不受地形的影響。
　　現在，將軍們規劃如何部署炮兵部隊，在防止誤傷的前提下（保證任何兩支炮兵部隊之間不能互相攻擊，即任何一支炮兵部隊都不在其他支炮兵部隊的攻擊范圍內），在整個地圖區域內最多能夠擺放多少我軍的炮兵部隊。

Input

第一行包含兩個由空格分割開的正整數，分別表示N和M；
　　接下來的N行，每一行含有連續的M個字符（‘P’或者‘H’），中間沒有空格。按順序表示地圖中每一行的數據。N≤100；M≤10。

Output

僅在第一行包含一個整數K，表示最多能擺放的炮兵部隊的數量。

Sample Input

5 4 PHPP PPHH PPPP PHPP PHHP

Sample Output

6

思路：

我們可以設當前為第$i$行，狀態為$l$，上一行狀態為$k$的最大值，再設一個$j$為上上行的狀態，即轉移方程為：
$$f[i][l][k]=max(f[i?1][k][j]+sum[l])$$
然后發現超時……
接下來思考，是否有些狀態無用
顯然答案是是的（但我不會證明）
即我們要篩掉一些無用的狀態，把剩下的存進數組里

代碼:

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<stack> #include<map> #include<cstring> using namespace std;const int MAXN=1<<10; const int N=110; int n, m, num, tot; int ma[MAXN], q[MAXN], sum[MAXN];bool VL_check(int x) {int cnt=0;while(x){if((x&1)&&cnt!=0)return 0;if(x&1)cnt=3;if(cnt!=0)cnt--;x>>=1;}return 1; } int VL_count(int x) {int c=0;while(x){c+=(x&1);x>>=1;}return c; } int main(){scanf("%d%d", &n, &m);for(int i=1; i<=n; i++)for(int j=1; j<=m; j++){char c;cin>>c;ma[i]=ma[i]<<1;if(c=='H')ma[i]++;}num=(1<<m);for(int i=0; i<num; i++){if(VL_check(i)){q[++tot]=i;sum[tot]=VL_count(i);}}int f[N][tot+1][tot+1];memset(f, 0, sizeof(f));for(int i=1; i<=n; i++)for(int j=1; j<=tot; j++)if(i==1||!(q[j]&ma[i-2]))for(int k=1; k<=tot; k++)if(!(q[j]&q[k])&&!(q[k]&ma[i-1]))for(int l=1; l<=tot; l++)if(!(q[l]&ma[i])&&!(q[l]&q[k])&&!(q[l]&q[j]))f[i][l][k]=max(f[i][l][k], f[i-1][k][j]+sum[l]);int ans=0;for(int j=1; j<=tot; j++)for(int k=1; k<=tot; k++)ans=max(ans, f[n][j][k]);printf("%d", ans);return 0; }

總結

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

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