题目大意：有一个大小为N * M的蛋糕，蛋糕上面有k根蜡烛，现在要求你在蛋糕上面铺1 * 2和2 * 1的巧克力 使得所铺的巧克力最少，且蛋糕上面没有空余地方可放巧克力了（只存在1 * 1的没铺的方格）
解题思路：1 ＊ 1的空闲方格由三行决定，上一行，当前行和下一行，如果只考虑两行的话，就比较难了 所以我们用dp[i][s1][s2]表示第i行的状态是s1，第i ＋ 1行的状态是s2的情况下放的最少巧克力数量 如此的话，可得到递推方程 dp[i][s1][s2] = min(dp[i][s1][s2], dp[i-1][s3][s4] + cnt) 解释上面方程的意思：在第i-1行的状态是s3，第i行的状态是s4的情况下，在第i行和第i＋1上铺巧克力，使第i行的状态变成s1，第i＋1行的状态变成s2，统计出铺在第i行和第i＋1行的巧克力数量cnt，这样的话，状态转移就完成了 现在的问题是如何更新，更新第i行的话有可能有影响到第i＋1行，所以传入两个状态，第i行和第i＋1行的状态，然后dfs暴力枚举出放的巧克力，统计一下即可 这里在更新第N行的时候，，需要用到第N＋1行，又因为第N＋1行是外界的行，所以最后的答案是 min(dp[N][s1][0]),第N＋1行不能被占用，如果被占用，就表示放的巧克力超出边界了
代码的话，参考了别人的，用了滚动数组来压缩空间
;g[80];int dp[2][S][S];int row, col, x, state_I, state_J;char str[N];int shift_l[N] = {1, 2, 4, 8, 16, 32, 64, 128, 256};void init() {memset(g, 0, sizeof(g));for (int i = 1; i <= row; i++) {scanf (“%s”, str);for (int j = 0; j < col; j++)g[i] = g[i] << 1 | (str[j] == ‘*’);}memset(dp, 0x3f, sizeof(dp));dp[0][shift_l[col] – 1][g[1]] = 0;x = 1;}void dfs(int r, int s1, int s2, int cnt) {if (r > 0 && (state_I & shift_l[r – 1]) == 0 && (s1 & shift_l[r – 1]) == 0)return ;if (r > 1 && (s1 & shift_l[r – 1]) == 0 && (s1 & shift_l[r – 2]) == 0)return ;if (r == col) {if (dp[x^1][state_I][state_J] != INF)dp[x][s1][s2] = min(dp[x][s1][s2], dp[x ^ 1][state_I][state_J] + cnt);return ;}dfs(r + 1, s1, s2, cnt);if((s1 & shift_l[r]) == 0 && (s2 & shift_l[r]) == 0)dfs(r + 1, s1 | shift_l[r], s2 | shift_l[r], cnt + 1);if(r < (col – 1) && (s1 & shift_l[r]) == 0 && (s1 & shift_l[r + 1]) == 0)dfs(r + 1, s1 | shift_l[r] | shift_l[r + 1], s2, cnt + 1);}void solve() {for (int r = 1; r <= row; r++) {for (int i = 0; i < shift_l[col]; i++)for (int j = 0; j < shift_l[col]; j++) {if (dp[x ^ 1][i][j] != INF) {state_I = i;state_J = j;dfs(0, j, g[r + 1], 0);}}memset(dp[x ^ 1], 0x3f, sizeof(dp[x ^ 1]));x ^= 1;}x ^= 1;int ans = INF;for(int i = 0; i < shift_l[col]; i++) {ans = min(ans, dp[x][i][0]);}printf(“%d\n”, ans);}int main() {scanf(“%d%d”, &row, &col);init();solve();return 0;}
慢慢学会了长大。流转的时光，
