由于递推的时候依赖于三个连续层的关系.一开始想着直接三重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; }
