由于递推的时候依赖于三个连续层的关系.一开始想着直接三重for循环,但是这里有个问题就是上一层的0位置上包括着上上层是0和1两种可能,而后者又对当前行有约束,因此该方法不行.当然有一个办法就是增加状态数,让状态能够表示是从1还是从0转移过来的.(这题有个解法是采用多进制的状态压缩). 网上瞄了别人的一眼解题报告. 瞬间顿悟,竟然三层之间发生关系,那么就直接把连续的两层记录起来,虽然说空间上不及多进制优美. 但是却能够去描述这些个问题.
代码如下:
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> using namespace std; /* 题意:给定一个矩阵,有点点能够放置部队,有的不行,部队能够进攻上下左右各2个格子,现在 问要求所有部队火力不能够覆盖友方部队,问最多能够摆放多少部队. 解法:其实这题单单就一行的状态来说,状态的约束条件更强,可以预见其合法状态也很少,何 况给定列本身就不超过10, 因此一行中的合法状态一定很少. 该题难点在于如何将上下 火力不覆盖友方部队很好的表示出来.一个可行的做法是对设置状态是dp[k][i][j]表示 第k层的状态为i,第i-1层状态为j时最多放置多少部队. 所以又动态方程: dp[k][i][j] = sum(dp[k-1][j][k]) 其中k满足不和i发生冲突 */ int N, M, sta[65], idx; // 当M=10的时候,合法的状态不超过65个 int G[105], dp[105][65][65]; // 该dp的第一维真正意义上表示一个状态,而不是状态的下表 void display(int x) { for (int i = 0; i < M; ++i) { if (x & (1 << i)) { printf("1 "); } else printf("0 "); } puts(""); getchar(); } void dfs(int pos, int statu, int dist) { if (pos == M) { sta[++idx] = statu; // display(statu); return; } dfs(pos+1, statu<<1, dist+1); if (dist >= 2) { dfs(pos+1, statu<<1|1, 0); } } bool legal(int x, int y) { return (x & y) == x; // 表示x状态的所有值都有对应的'P' } bool judge(int x, int y) { return !(x & y); // 如果没有对应的1 } int get(int x) { int ret = 0; for (int i = 0; i < M; ++i) { if (x & (1 << i)) { ++ret; } } return ret; } int DP() { int ret = 0; memset(dp, 0, sizeof (dp)); if (N == 1) { // 如果是只有一层的话,就特殊处理一下 for (int i = 1; i <= idx; ++i) { if (legal(sta[i], G[1])) { ret = max(ret, get(sta[i])); } } return ret; } // 初始化第一,二层的状态 for (int i = 1; i <= idx; ++i) { // 枚举第二层要更新的状态 for (int j = 1; j <= idx; ++j) { // 枚举第一层的状态 if (legal(sta[i], G[2]) && legal(sta[j], G[1]) && judge(sta[i], sta[j])) { dp[2][i][j] = get(sta[i]) + get(sta[j]); } } } for (int k = 3; k <= N; ++k) { for (int i = 1; i <= idx; ++i) { for (int j = 1; j <= idx; ++j) { if (!judge(sta[i], sta[j]) || !legal(sta[i], G[k]) || !legal(sta[j], G[k-1])) { continue; } for (int m = 1; m <= idx; ++m) { if (judge(sta[i], sta[m]) && judge(sta[j], sta[m])) { dp[k][i][j] = max(dp[k][i][j], dp[k-1][j][m]); } } dp[k][i][j] += get(sta[i]); } } } for (int i = 1; i <= idx; ++i) { for (int j = 1; j <= idx; ++j) { ret = max(ret, dp[N][i][j]); } } return ret; } int main() { char str[15]; while (scanf("%d %d", &N, &M) == 2) { idx = 0, dfs(0, 0, 2); // printf("idx = %d\n", idx); memset(G, 0, sizeof (G)); for (int i = 1; i <= N; ++i) { scanf("%s", str); for (int j = 0; j < M; ++j) { G[i] <<= 1, G[i] |= str[j] == 'P'; // 当等于P的时候能够放置部队 } } printf("%d\n", DP()); } return 0; }