状态压缩DP 树形DP 以及记忆化搜索

状态压缩DP

题目一

图源ACWING

解题思路

原题解链接：https://www.acwing.com/solution/content/15616/
在这里插入图片描述
补充：
解释一下st[j | k] ：已经知道st[]数组表示的是这一列没有连续奇数个0的情况，我们要考虑的是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，还要考虑自己这一列（i-1列）横插到第i列的比如第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，那么合在第i-1列，到底有多少个1呢？自然想到的就是这两个操作共同的结果：两个状态或。 j | k = 01000 | 10101 = 11101 这个 j|k 就是当前第i-1列的到底有几个1，即哪几行是横着放格子的

代码实现

{int n, m;while (cin >> n >> m, n || m){for (int i = 0; i < 1 << n; i ++ )//i表示不同种的摆放策略（不考虑其它列的影响下）//如10010, 01110, 11101等等， 因此i < 1 << n{int cnt = 0;st[i] = true;for (int j = 0; j < n; j ++ ){if (i >> j & 1){if (cnt & 1)//保证一列上连续的空格数不能为奇数， 如果是奇数还要在下一行放横方块，会导致用竖方块填不满{st[i] = false;break;}}else{cnt ++;}}//当倒数第二行放了方块，倒数第一行不放方块也是不能通过的，因为塞不进一个竖方块了if (cnt & 1){st[i] = false;}}memset(f, 0, sizeof f);f[0][0] = 1;for (int i = 1; i <= m; i ++ ){for (int k = 0; k < 1 << n; k ++ ){for (int j = 0; j < 1 << n; j ++ ){if (st[k | j] && ((j & k) == 0)){f[i][j] += f[i - 1][k];}}}}cout << f[m][0] << endl;}return 0;
}

题目二

在这里插入图片描述

解题思路

原题解：https://www.acwing.com/solution/content/18533/
在这里插入图片描述
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);意思为：以j为终点，i的选择情况下的最短距离 = 以k为终点，不包含j的选择情况下的距离 + k到j的距离。

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N = 20, M = 1 << 20;
int f[M][N], w[N][N];int main()
{int n;cin >> n;for (int i = 0; i < n; i ++ ){for (int j = 0; j < n; j ++ ){scanf("%d", &w[i][j]);}}memset(f, 0x3f, sizeof f);f[1][0] = 0;for (int i = 0; i < 1 << n; i ++ ){for (int j = 0; j < n; j ++){if (i >> j & 1){for (int k = 0; k < n; k ++ ){if (i >> k & 1){f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);}}}}}cout << f[(1 << n) - 1][n - 1];return 0;
}

树形DP

题目

在这里插入图片描述

解题思路

原题解：https://www.acwing.com/solution/content/105019/
在这里插入图片描述
最好脑补一下dfs的过程，便于理解

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N = 6010;int f[N][2], happy[N];
int h[N], e[N], ne[N], idx;
bool has_father[N];void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx ++;
}void dfs(int u)
{f[u][1] = happy[u];for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];dfs(j);f[u][0] += max(f[j][1], f[j][0]);f[u][1] += f[j][0];}
}int main()
{memset(h, -1, sizeof h);int n;cin >> n;for (int i = 1; i <= n; i ++ ){scanf("%d", &happy[i]);}int a, b;for (int i = 1; i < n; i ++ ){scanf("%d%d", &a, &b);has_father[a] = true;add(b, a);}int root = 1;while (has_father[root]){root ++;}dfs(root);cout << max(f[root][1], f[root][0]);return 0;
}

记忆化搜索

题目

在这里插入图片描述

解题思路

原题解：https://www.acwing.com/solution/content/106207/
在这里插入图片描述

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N = 310;int h[N][N], f[N][N];
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
int n, m;int dp(int x, int y)
{int &v = f[x][y];if (v != -1){return v;}v = 1;for (int i = 0; i <= 3; i ++ ){int a = x + dx[i], b = y + dy[i];if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] > h[x][y]){v = max(v, dp(a, b) + 1);}}return v;
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= m; j ++ ){scanf("%d", &h[i][j]);}}memset(f, -1, sizeof f);int res = 0;for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= m; j ++ ){res = max(res, dp(i, j));}}cout << res;return 0;
}