題目鏈接
題意：給出一張n * m的地圖，其中 有的地方能放大炮，有的地方不能，大炮與上下左右兩個單位范圍內會相互攻擊，問最多能放幾個大炮
11式輪式突擊炮數據？能放大炮為1不能放大炮為0，把每一行看做一個狀態，要除去同一行與前面兩個相鄰的情況，然后在除去與上面兩行相鄰的情況，因為涉及前面兩行所以多設一維狀態
dp[i][j][k]表示 第 i 行 狀態為k時，第i - 1行狀態為j，
那么dp[i][j][k] = max ( dp[i][j][k], dp[i - 1][t][j] + num[k])； num[k]表示第i行可以放多少門大炮，也就是k狀態下1的個數
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int state[200], num[200]; int cur[110]; char g[110][20]; int dp[110][200][200]; int n, m, top, total; inline bool is_ok(int x) {if (x & (x << 1))return 0;if (x & (x << 2))return 0;return 1; } int jcount(int x) {int cnt = 0;for (int i = 0; i < 12; i++)if (x & (1 << i))cnt++;return cnt; } int fit(int x, int i) {if (x & cur[i])return 0;return 1; } void init() {top = 0;total = 1 << m;for (int i = 0; i < total; i++){if (is_ok(i))state[++top] = i;} } int main() {while (scanf("%d%d", &n, &m) != EOF){init();for (int i = 1; i <= n; i++){cur[i] = 0;scanf("%s", g[i] + 1);for(int j = 1; j <= m; j++)if (g[i][j] == 'H')cur[i] += (1 << (j - 1) ); //同上一題一樣將不能放炮的設為1，這樣 & 的話只要非0就不行，因為一定含有不能放炮的而放炮了，0是允許放炮，但是放不放都行，也就是0,1隨便，都是可以的 }memset(dp, -1, sizeof(dp));int ans = -1;for (int i = 1; i <= top; i++){num[i] = jcount(state[i]); // 求出每一種狀態下能放得炮數if (!fit(state[i], 1))continue;dp[1][1][i] = num[i]; //第一行狀態為state[i],第0行狀態為state[1] = 0ans = max(ans, num[i]);}for (int i = 2; i <= n; i++){for (int t = 1; t <= top; t++){if (!fit(state[t], i))continue;for (int j = 1; j <= top; j++) // 第 i - 1行的情況 {if (state[t] & state[j])continue;for (int k = 1; k <= top; k++) //第i - 2行的情況 {if (state[t] & state[k])continue;if (dp[i - 1][k][j] != -1) // 不符合要求的，dp[1][1][其他] ,而第0行其他狀態都沒有 {dp[i][j][t] = max(dp[i][j][t], dp[i - 1][k][j] + num[t]);ans = max(ans, dp[i][j][t]);}}}}}printf("%d\n", ans);}return 0; }
poj1741。?
