寒假：Day4

今天继续复习搞基础课&＃xff0c;加油&＃xff01;

树形DP

每一个节点都分为选和不选两种状态&＃xff0c;选为f[i, 1]&＃xff0c;不选为f[i, 0]&＃xff0c;每一个节点想要最大&＃xff0c;他的每一个子树权值都必须最大&＃xff0c;递归即可

不选择根节点的最大值&＃xff1a;
$$f[i,0]\&＃61;max(f[s1,0],f[s1,1])\&＃43;max(f[s2,0],f[s2,1])\&＃43;...\&＃43;max(f[sk,0],f[sk,1])$$
选择根节点的最大值&＃xff1a;
$$f[i,1]\&＃61;f[s1,0]\&＃43;f[s2,0]\&＃43;f[s3,0]\&＃43;.....\&＃43;f[sk,0]$$
AcWing 285. 没有上司的舞会 - AcWing

#include
using namespace std;
const int N &＃61; 6010;
int n;
int w[N];
int h[N], e[N], ne[N], idx;
bool st[N]; // 用来判断是否有父节点&＃xff0c;查找根节点
int f[N][2];void add(int a, int b)
{e[idx] &＃61; b, ne[idx] &＃61; h[a], h[a] &＃61; idx&＃43;&＃43;;
}void dfs(int u){f[u][1] &＃61; w[u];for (int i &＃61; h[u]; i !&＃61; -1; i &＃61; ne[i]) { int j &＃61; e[i];dfs(j);f[u][0] &＃43;&＃61; max(f[j][0], f[j][1]); // 状态转移f[u][1] &＃43;&＃61; f[j][0];}
}int main(void)
{cin >> n ;for (int i &＃61; 1 ; i <&＃61; n ; i &＃43;&＃43;) cin >> w[i];memset(h, -1, sizeof h);for (int i &＃61; 0; i < n - 1; i&＃43;&＃43;) {int a, b ;cin >> a >> b ;add(b, a);st[a] &＃61; true;}int root &＃61; 1;while (st[root]) root&＃43;&＃43;; //找到根节点dfs(root);cout << max(f[root][0], f[root][1]) << endl ;return 0;
}


记忆化搜索

顾名思义&＃xff0c;就是把每一次搜索的过程中的有用信息都存下来&＃xff0c;这样下一次搜索如果也要用到这个信息&＃xff0c;就可以直接调用而不用再次搜索

AcWing 901. 滑雪 - AcWing

#include
using namespace std;const int N &＃61; 310;
int n, m;
int h[N][N];
int f[N][N];int dx[] &＃61; {-1, 0, 1, 0};
int dy[] &＃61; {0, 1, 0, -1};int dp(int x, int y)
{int &v &＃61; f[x][y]; // v 等价于 f[x][y]if (v !&＃61; -1) return v; // 如果他已经被搜过了&＃xff0c;直接返回值v &＃61; 1; // 至少为1for (int i &＃61; 0; i < 4; i&＃43;&＃43;) {int a &＃61; x &＃43; dx[i], b &＃61; y &＃43; dy[i];if (a >&＃61; 1 && a <&＃61; n && b >&＃61; 1 && b <&＃61; m && h[a][b] < h[x][y])v &＃61; max(v, dp(a, b) &＃43; 1);}return v;
}int main(void)
{scanf("%d %d", &n, &m);for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) {for (int j &＃61; 1; j <&＃61; m; j&＃43;&＃43;) {scanf("%d", &h[i][j]);}}memset(f, -1, sizeof f); // 表示每个状态都没有被算过int res &＃61; 0;for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) {for (int j &＃61; 1; j <&＃61; m; j&＃43;&＃43;) {res &＃61; max(res, dp(i, j));}}cout << res << endl ;return 0;
}


区间DP

区间dp &＃xff0c;指在一段区间上进行动态规划&＃xff0c;一般做法是由长度较小的区间往长度较大的区间进行递推&＃xff0c;最终得到整个区间的答案&＃xff0c;而边界就是长度为1以及2的区间。

282. 石子合并 - AcWing题库

#include
using namespace std;
const int N &＃61; 310;
int n;
int s[N]; // 前缀和
int f[N][N];int main(void)
{cin >> n;for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) cin >> s[i], s[i] &＃43;&＃61; s[i - 1]; // 前缀和for (int len &＃61; 2; len <&＃61; n; len&＃43;&＃43;) { // 先枚举区间长度for (int i &＃61; 1; i &＃43; len - 1 <&＃61; n; i&＃43;&＃43;) { // 再枚举区间左端点int j &＃61; i &＃43; len - 1;f[i][j] &＃61; 1e8;for (int k &＃61; i; k < j; k&＃43;&＃43;) { // 枚举区间内每一种合并方式求最小f[i][j] &＃61; min(f[i][j], f[i][k] &＃43; f[k &＃43; 1][j] &＃43; s[j] - s[i - 1]);}}}cout << f[1][n] << endl ;return 0;
}


计数DP

类比完全背包问题&＃xff0c;前i个物品中任选且体积恰好为j的方案数f[i, j]&＃xff0c;对第i个物品进行分集合&＃xff0c;选一个第i个物品使得体积恰好为j就是f[i, j - i]&＃xff0c;选两个第i个物品使得体积恰好为j就是f[i, j - 2i]&＃xff0c;以此类推方案数就是总和
$$f[i,j]\&＃61;f[i-1,j]\&＃43;f[i,j-i]\&＃43;f[i,j-2\ast i]\&＃43;f[i,j-3\ast i]\&＃43;...\&＃43;f[i,j-s\ast i]$$
利用完全背包优化方式&＃xff1a;
$$f[i,j-i]\&＃61;f[i-1,j-i]\&＃43;f[i,j-2\ast i]\&＃43;f[i,j-3\ast i]\&＃43;...\&＃43;f[i,j-s\ast i]$$
可得&＃xff1a;$f[i,j]\&＃61;f[i-1,j]\&＃43;f[i,j-i]$

然后优化成一维空间&＃xff0c;变成$f[j]\&＃61;f[j]\&＃43;f[j-i]$即可

AcWing 900. 整数划分 - AcWing

#include
using namespace std;
const int N &＃61; 1010, mod &＃61; 1e9 &＃43; 7;
int f[N];
int main(void)
{int n;cin >> n;f[0] &＃61; 1;for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) {for (int j &＃61; i; j <&＃61; n; j&＃43;&＃43;) {f[j] &＃61; (f[j] &＃43; f[j - i]) % mod;}}cout << f[n] << endl ;return 0;
}