#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string.h> #include <string>using namespace std;const int MAXN = 100 + 1; //陣地行數(shù) const int MAXM = 10 + 1; //陣地列數(shù) const int State_Num = 60 + 1; //陣地列狀態(tài)的壓縮總數(shù),合法狀態(tài)總數(shù)最多60int dp[MAXN][State_Num][State_Num], cur[MAXN], state[State_Num], tot; char field[MAXN][MAXM]; //儲(chǔ)存陣地 int n, m; //陣地規(guī)模/* 因?yàn)閚 <= 100, m <= 10,將陣地的列壓縮。 dp[i][j][k]表示當(dāng)?shù)趇行布置結(jié)束后,第i行的布置狀態(tài)為j的情況下, 第i - 1行的狀態(tài)為k,所能布置的最多的炮兵。

依據(jù)題意,我們能夠刪除一些狀態(tài)。 刪除的狀態(tài)有： 1.山地不能布置炮兵 2.炮兵不能在垂直和水平的線上兩格相鄰。 cur[]數(shù)組用于儲(chǔ)存輸入的合法局面 state[]數(shù)組用于儲(chǔ)存相鄰的合法局面 */ bool ok(int x) { return !((x & (x << 1)) || (x & (x << 2))); } void init() //保留不兩格相鄰的 { int limit = (1 << m); tot = 0; for (int i = 0; i < limit; i++) { if (ok(i)) state[tot++] = i; } } bool yes(int x, int i) { return !(x & cur[i]); } int cal(int x) { int res = 0; while (x) { if (x & 1) res++; x >>= 1; } return res; } void input() { while (scanf("%d %d", &n, &m) != EOF) //輸入 { init(); memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) { scanf("%s", field[i]), cur[i] = 0; for (int j = 0; j < m; j++) if (field[i][j] == 'H') cur[i] += (1 << (m - j - 1)); //用于推斷狀態(tài)是否合法(1) } for (int i = 0; i < tot; i++) //初始化第一行 { if (!yes(state[i], 0)) continue; for (int j = 0; j < tot; j++) { dp[0][i][j] = cal(state[i]); } } for (int i = 1; i < n; i++) //計(jì)算當(dāng)前行，枚舉上兩行的狀態(tài) { for (int j = 0; j < tot; j++) //枚舉當(dāng)前行的狀態(tài) { if (!yes(state[j], i)) continue; for (int k = 0; k < tot; k++) { if (!yes(state[k], i - 1)) continue; for (int l = 0; l < tot; l++) { if (!yes(state[l], i - 2)) continue; if (((state[j] & state[k]) == 0) && ((state[j] & state[l]) == 0) && ((state[k] & state[l]) == 0)) { dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + cal(state[j])); } } } } } int ans = 0; //計(jì)算答案 for (int i = 0; i < tot; i++) for (int j = 0; j < tot; j++) ans = max(ans, dp[n - 1][i][j]); cout << ans << endl; } } int main() { input(); return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/mengfanrong/p/5142755.html

總結(jié)

以上是生活随笔為你收集整理的poj1185炮兵阵地的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。