动态规划多阶段一个重要的特性就是无后效性。无后效性就是值对于某个给定的阶段状态，它以前各阶段的状态无法
直接影响它未来的发展，而只能通过当前的这个状态。换句话说影响当前阶段状态只可能是前一阶段的状态；
这段文字是在这篇博客中看到的 博客
题目1： 蒙德里安的梦想
分析：
这个同学的题解写的真的不错：题解
时间复杂度：
代码区：
#include#include #include using namespace std; const int N = 12, M = 1 << 11; int n, m; bool st[M]; vector state[M]; long long f[N][M]; int main() { while(cin >> n >> m, n || m) { for(int i = 0; i < 1 << n; i ++) { int cnt = 0; bool is_vaild = true; for(int j = 0; j < n; j ++) { if(i >> j & 1) { if(cnt & 1) { is_vaild = false; break; } } else cnt ++; } if(cnt & 1) is_vaild = false; st[i] = is_vaild; } for(int i = 0; i < 1 << n; i ++) { state[i].clear(); for(int j = 0; j < 1 << n; j ++) { if((i & j) == 0 && st[i | j]) { state[i].push_back(j); } } } memset(f, 0, sizeof f); f[0][0] = 1; for(int i = 1; i <= m; i ++) { for(int j = 0; j < 1 << n; j ++) { for(auto item : state[j]) f[i][j] += f[i - 1][item]; } } cout << f[m][0] << endl; } return 0; }
题目2： 小国王
分析：时间复杂度： O ( n 3 ∗ m ∗ 2 n ∗ 2 n ) O(n^3 * m * 2^n * 2^n) O(n3∗m∗2n∗2n)，会超时
优化方式： 优化方式，预处理。预处理后合法的状态会减少。
代码区：
#include#include #include using namespace std; typedef long long LL; const int N = 12, M = 1 << 10, K = 110; int n, m; vector state; vector head[M]; int cnt[M]; LL f[N][K][M]; bool check(int s) { for(int i = 0; i < n; i ++) { if((s >> i & 1) && (s >> i + 1 & 1)) return false; } return true; } int count(int s) { int res = 0; for(int i = 0; i < n; i ++) res += s >> i & 1; return res; } int main() { cin >> n >> m; for(int i = 0; i < 1 << n; i ++) { if(check(i)) { state.push_back(i); cnt[i] = count(i); } } for(int i = 0; i < state.size(); i ++) { for(int j = 0; j < state.size(); j ++) { if((state[i] & state[j]) == 0 && (check(state[i] | state[j]))) head[i].push_back(j); } } f[0][0][0] = 1; for(int i = 1; i <= n + 1; i ++) { for(int j = 0; j <= m; j ++) { for(int a = 0; a < state.size(); a ++) { for(auto item : head[a]) { int k = cnt[state[a]]; if(j - k >= cnt[state[item]]) f[i][j][state[a]] += f[i - 1][j - k][state[item]]; } } } } cout << f[n + 1][m][0] << endl; return 0; }
题目3： 玉米田
分析：时间复杂度：
代码区：
#include#include #include #include using namespace std; const int N = 14, M = 1 << 12, mod = 1e8; int n, m; int w[N]; vector state; vector head[M]; int f[N][M]; bool check(int s) { for(int i = 0; i + 1 < m; i ++) { if((s >> i & 1) && (s >> i + 1 & 1) ) return false; } return true; } int main() { cin >> n >> m; for(int i = 1; i <= n; i ++) { for(int j = 0; j < m; j ++) { int t; cin >> t; w[i] += !t * (1 << j); } } for(int i = 0; i < 1 << m; i ++) { if(check(i)) { state.push_back(i); } } for(int i = 0; i < state.size(); i ++) { for(int j = 0; j < state.size(); j ++) { if((state[i] & state[j]) == 0) head[i].push_back(j); } } f[0][0] = 1; for(int i = 1; i <= n + 1; i ++) { for(int j = 0; j < state.size(); j ++) { if((state[j] & w[i]) == 0) { for(auto item : head[j]) { f[i][j] = (f[i][j] + f[i - 1][item]) % mod; } } } } cout << f[n + 1][0] << endl; return 0; }
题目4： 炮兵阵地
分析：时间复杂度：
代码区：
#include#include #include using namespace std; const int N = 110, M = 1 << 10; int n, m; int g[N]; int cnt[M]; vector state; int f[2][M][M]; bool check(int s) { for(int i = 0; i < m; i ++) { if((s >> i & 1) && ( (s >> i + 1 & 1) || (s >> i + 2 & 1) )) return false; } return true; } int count(int s) { int res = 0; for(int i = 0; i < m; i ++) res += s >> i & 1; return res; } int main() { cin >> n >> m; for(int i = 1; i <= n; i ++) { for(int j = 0; j < m; j ++) { char c; cin >> c; g[i] += (c == 'H') << j; } } for(int i = 0; i < 1 << m; i ++) { if(check(i)) { state.push_back(i); cnt[i] = count(i); } } for(int i = 1; i <= n; i ++) { for(int j = 0; j < state.size(); j ++) { for(int k = 0; k < state.size(); k ++) { for(int u = 0; u < state.size(); u ++) { int a = state[j], b= state[k], c = state[u]; if(a & b || a & c || b & c) continue; if(a & g[i - 1] || b & g[i]) continue; f[i & 1][k][j] = max(f[i & 1][k][j], f[i - 1 & 1][j][u] + cnt[b]); } } } } int res = 0; for(int i = 0; i <= state.size(); i ++) { for(int j = 0; j <= state.size(); j ++) res = max(res, f[n & 1][i][j]); } cout << res << endl; return 0; }
