ACM（暑假篇 day2)

本来想继续学难度高一点的区间dp问题发现好像能力不够还是把这些基础的dp问题掌握在进阶吧这篇就以树形dp为主将树形dp的基础问题解决搞懂完成阶段一的主要任务。这类问题算是结合了深搜和dp不断的递归求出最小值和最大值需要熟练的掌握递归的方法。1.P1352 没有上司的舞会1核心思路这种题我已经看过很多类似的但是以前永远都写不出。树形dp的核心就在于选与不选而这题有根节点作保障我们可以从根节点开始判断选or不选设一个dp[N][2]也就是说dp[N][0]的时候为不选dp[N][1]的时候为选一维代表的是其编号。2寻找根节点为搜索做准备想要递归我们必须找到源头也就是根节点依据题目的要求总会有一个是老大我们先假设所有的编号都是根for(int i1;in;i) { cin r[i]; is_root[i]true; }然后根据第 (n2) 到第 2n 行的输入导入父亲节点和子节点再将这些子节点从is_root里面排查出去for(int i0;in-1;i) { int l,k; cin l k; son[k].push_back(l); is_root[l]false; }最后再设一个root从1到n循环一遍找出那个唯一为true的根节点int root; for(int i1;in;i) { if(is_root[i]) rooti; }这样我们既找出了根节点也将所有父与子关系的节点整理出来了为我们后续执行递归dp做了充足的准备。3编写核心代码寻找最大快乐值思路理清也做好了前提准备现在绝对可以看懂代码以及对于掌握递归的同学能几乎想出接下来的步骤定义一个dfs函数将root值导入进去0的时候是不选1的时候是选再去它的子节点里面找又从子节点里面找子节点依次循环下去最后又把值传入根节点代码如下void dfs(int u) { dp[u][0]0; dp[u][1]r[u]; for(int v:son[u]) { dfs(v); dp[u][0]max(dp[v][0],dp[v][1]); dp[u][1]dp[v][0]; } }这题就是要将dfs插入正确的位置而不是插入在循环外也不是在循环的末尾。本题完整代码如下#include bits/stdc.h using namespace std; typedef long long ll; const int N6e310; int r[N]; int dp[N][2]; vector int son[N]; bool is_root[N]; void dfs(int u) { dp[u][0]0; dp[u][1]r[u]; for(int v:son[u]) { dfs(v); dp[u][0]max(dp[v][0],dp[v][1]); dp[u][1]dp[v][0]; } } int main() { int n; cin n; for(int i1;in;i) { cin r[i]; is_root[i]true; } for(int i0;in-1;i) { int l,k; cin l k; son[k].push_back(l); is_root[l]false; } int root; for(int i1;in;i) { if(is_root[i]) rooti; } dfs(root); cout max(dp[root][1],dp[root][0]); return 0; }2.P2016 [SEERC 2000] 战略游戏1设计思路这题是个无根树且没有方向可以看成一个图每个点都可以为出发点既是父节点也是子节点。这道题的核心解题方法同样也是选与不选当选了一个点士兵那么周围的点按道理就不需要选了除特殊情况外。懂得这个道理我们可以快速入手了。2做好前提准备将每个连接的节点都互相导入成对方的父节点和子节点代码如下int n; cin n; for(int i 0; i n; i) { int x, k; cin x k; while(k--) { int r; cin r; son[x].push_back(r); son[r].push_back(x); } }3全面考虑完成核心代码void dfs(int u, int fa) { dp[u][1] 1; // 当前点放士兵 dp[u][0] 0; // 当前点不放 for(int v : son[u]) { if(v fa) continue; dfs(v, u); dp[u][1] min(dp[v][1],dp[v][0]); dp[u][0] dp[v][1]; } }核心的dfs代码和上一题的代码大同小异但是我们会发现dfs有两个变量一个u和一个多出的fau大家都理解就是导入的根节点这里我们第一个导入的是1那么fa又是什么呢fa是father的简写这里的作用就是当遍历到1的子节点2时经过递归2的子节点含有1、3、4那么又会重复遍历1和2这个选项导致死循环所以用一个fa帮助我们解决这个问题。而现在我们会发现为什么我们在dp[u][1] min(dp[v][1],dp[v][0]);要使用min因为dp[v][0]不肯定要比dp[v][1]小吗其实不然例如我们以根节点为1为例初始选1的话那么我们选择的安放点就为1、3、4。如果不选1那么选择点为2、4、6。而我们会发现最好的放置点应该为2、4两个放置点这也解释了为什么我们需要使用min来找出最小值。本题完整代码如下#include bits/stdc.h using namespace std; const int N 1510; vectorint son[N]; int dp[N][2]; // 带父亲防回走 void dfs(int u, int fa) { dp[u][1] 1; // 当前点放士兵 dp[u][0] 0; // 当前点不放 for(int v : son[u]) { if(v fa) continue; dfs(v, u); dp[u][1] min(dp[v][1],dp[v][0]); dp[u][0] dp[v][1]; } } int main() { int n; cin n; for(int i 0; i n; i) { int x, k; cin x k; while(k--) { int r; cin r; son[x].push_back(r); son[r].push_back(x); } } dfs(0, -1); cout min(dp[0][0], dp[0][1]); return 0; }3.P12317 [蓝桥杯 2024 国 C] 树的结点值1拆解题意理清思路很直观的树形dp题依然是通过深搜dp的方法有上面两个题目给我们打基础写这题多多少少会有一点思路。想要知道某节点的值我们需要知道在它之下所有节点的奇偶性但我们不能通过暴力搜索的方式将这个节点之下的所有奇偶的值都获取我们通过递归可以从最下层一层一层的传上来。2实现代码功能我们可以定义两个数组一个记录奇数的个数一个记录偶数的个数。我们通过深搜的方式将底层的奇偶值一层一层的向上传上来如果该节点是偶数那么我们就在偶数节点的个数上加上一奇数节点的值不变反之同理。#include bits/stdc.h using namespace std; const int N2e510; vector int f[N]; int cnt_0[N],cnt_1[N]; void dfs(int u) { if(u%20) { cnt_0[u]1; cnt_1[u]0; } else { cnt_0[u]0; cnt_1[u]1; } for(int v:f[u]) { dfs(v); cnt_0[u]cnt_0[v]; cnt_1[u]cnt_1[v]; } } int main() { int n; cin n; for(int i2;in;i) { int fi; cin fi; f[fi].push_back(i); } dfs(1); for(int i1;in;i) { if(i%20) cout cnt_0[i]; else cout cnt_1[i]; cout endl; } return 0; }可以说这题甚至都没有用到dp但是思路和上面两道dp的题大同小异将dp拆分为两个代表奇偶数个数的数组。4.P14919 [GESP202512 六级] 路径覆盖1理清思路构思题解这题是我认为很有意思的一道题最开始我还没有理解这道题的意思以为是每个子节点结果发现是叶子节点向上传输需要经过一个染黑的节点。但是我们要怎么找到那个叶子节点并且能直接往上回溯这是我当时想不到的点。这题的核心解题思路就是快速判断是否为叶子节点将数据往上传输。2完成代码这题的代码的强大之处就是既找出了叶子节点也找到了最小的值真的能理解其微妙之处的才能感受到代码的力量如此精简没有任何累赘。代码如下#include bits/stdc.h using namespace std; const int N1e510; vector int son[N]; int dp[N]; long long c[N]; void dfs(int u) { long long sum0; bool is_leaftrue; for(int v:son[u]) { is_leaffalse; dfs(v); sum dp[v]; } if(is_leaf) { dp[u]c[u]; } else { dp[u]min(sum,c[u]); } } int main() { int n; cin n; for(int i2;in;i) { int f; cin f; son[f].push_back(i); } for(int i1;in;i) { cin c[i]; } dfs(1); cout dp[1]; return 0; }这个sum的作用不仅仅是简单的统计而我认为此代码的精妙之处就是当4、5的染黑值传上来之后我们需要判单它们的父节点2是否能代替两个节点的染黑值因为2在4、5两个叶子节点的路径上所以此时的sum不是全局的sum而是当下2节点之下的子节点的sum值将这个sum与2的值作比较就解决了这个代码最核心的几个问题。这次的分享就到此为止这算是几个比较基础的树形dp题目也许3、4题的解析比较简略但是我已经在最初的几道题解析了这类题目的核心思想我相信只要理解了这类思想都可以理解我之后的分析。最后想说下我个人在最近写题的一些心得在我身边很多人的学习新知识的方法都是通过大量的写题以及抄写理解但我的方法不一样在刚刚起步的时候我认为我需要花费更多的时间去拆解这些知识点的内涵我初期写题花费的时间也许是别人的几倍我写一道题可能就花费了1到2个小时去疯狂拆解题意去找网课学习但是我觉得题目在精不在多若不去理解题目深层的含义我认为至少对于我来说我的路是走不远的永远无法向更高难度的题目进阶。