N ∗ M N*M N∗M的图， H H H表示山地， P P P表示平原，山地不能布置炮兵，平原可以布置炮兵， 1 1 1个炮兵影响的范围是上下左右各两个区域，问放最多能放几个炮兵。
先将读入的图转化为二进制数 p i c [ i ] pic[i] pic[i](这里 1 1 1表示山地， 0 0 0表示平原)，因为同一行状态最多有 1024 1024 1024个，而根据题目限制可行状态其实只有 70 70 70个左右，所以预处理同行所有可行状态 s t a [ i ] sta[i] sta[i](这里 1 1 1表示有兵， 0 0 0表示没有兵)及其所需的炮兵数 n u m [ i ] num[i] num[i]和第一行所有可行状态需要的炮兵数，从上至下状态转移，状态转移方程： d p [ i ] [ j ] [ k ] = m a x ( d p [ i ] [ j ] [ k ] , d p [ i − 1 ] [ k ] [ l ] + n u m [ j ] ) dp[i][j][k]=max(dp[i][j][k], dp[i-1][k][l]+num[j]) dp[i][j][k]=max(dp[i][j][k],dp[i−1][k][l]+num[j]) 其中 i i i表示当前行， j j j表示当前行状态， k k k表示上一行状态， l l l表示上上行状态。 转移的时候要注意很多条件判断。 1. 1. 1.当前行状态 j j j不能与当前行图 p i c [ i ] pic[i] pic[i]冲突。 2. 2. 2.上一行状态 k k k不能与当前行状态 j j j冲突，并且不能与上一行图 p i c [ i − 1 ] pic[i-1] pic[i−1]冲突。 3. 3. 3.上上行状态 l l l不能与 k 、 j k、j k、j冲突，不能与上上行图 p i c [ i − 2 ] pic[i-2] pic[i−2]冲突。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100 + 5; int n, m, cnt, ans, maxsta, num[maxn], sta[maxn], pic[maxn], dp[maxn][maxn][maxn]; char str[15]; int cal(int x){ int sum = 0; while(x){ if(x & 1) sum++; x >>= 1; } return sum; } int main(){ scanf("%d %d", &n, &m); maxsta = 1 << m; for(int i = 1; i <= n; i++){ scanf("%s", str + 1); for(int j = 1; j <= m; j++){ if(str[j] == 'H') pic[i] += (1 << (j - 1)); } } for(int i = 0; i < maxsta; i++) if(!(i & (i << 1)) && !(i & (i << 2))){ sta[++cnt] = i, num[cnt] = cal(i);注意这里枚举的是放兵的状态要和图的状态分开来看。 }//放兵状态:1表示有兵 0表示无兵,图的状态:1表示山地 0表示平原,这样子做容易判断兵是否在山地上！ for(int i = 1; i <= cnt; i++) if(!(sta[i] & pic[1])){ dp[1][i][1] = num[i]; } for(int i = 2; i <= n; i++){ for(int j = 1; j <= cnt; j++){//当前i行状态j if(sta[j] & pic[i]) continue; for(int k = 1; k <= cnt; k++){//上一行状态k if(sta[j] & sta[k] || sta[k] & pic[i - 1]) continue; for(int l = 1; l <= cnt; l++){//上上行状态l if(sta[l] & pic[i - 2] || sta[l] & sta[j] || sta[l] & sta[k]) continue; dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + num[j]); } } } } for(int i = 1; i <= cnt; i++) for(int j = 1; j <= cnt; j++) ans = max(ans, dp[n][i][j]); printf("%d\n", ans); return 0; }