本题的树上子链的说法是我第一次见，树上子链指的是树上的任意一条链，换句话说就是树上任意两点中最长的那一个。但这题不是以长度定的，每个节点都有权值，要的是权值和最长的子链。 所以我们对于某一个节点，选取儿子中最长和次长。然后加上节点本身就是答案了。 但在这里面寻找最长和次长的方式很巧妙，先贴代码： res = max(res, dp[x]+dp[y]); dp[x] = max(dp[x], dp[y]+val[x]); 在这里面先更新res，res是最终的结果。然后更新dp[x]是在寻找哪个加上本节点最大。那么在寻找过...

本题中很大不同点在于他给的是边的数值，而正常的树的问题是在节点上给值。那么我们采用边值下放点的做法，这样就是正常的树问题了。 那么对于某一个节点来说它保留j个节点所得到的最大苹果树取决于这j个节点来自于左边子树多少，来自右边子树多少。又因为他自身就有一个节点所以状态转移方程为：  dp[i][need] = max(dp[i][need], num_l+num_r+tree[i].val); 但是要注意对于第一个节点传递的时候需要传递q+1，因为别的节点都有父亲，所以他们本身也贡献一个树枝。但根节点没有，为了保证一致性所以传递q+1。 还有这题使用记忆化搜索最...

本题是点的最小覆盖集问题，是一个树形dp问题。 对于某一个节点来说他能通信来自于他父亲以及他儿子节点以及他自身。那么dp[n][3]表示某个节点三这种情况下的最小值。 0：靠父亲。 1：靠自己。 2：靠儿子。 那么对于靠自己和靠父亲来说很简单的能写出状态转移方程： dp[i][0] = (儿子节点的和)min(dp[u][1],dp[u][2]); dp[i][1] = (儿子节点的和)min(dp[u][0],dp[u][1],dp[u][2]); 对于最后靠儿子的情况，只要有一个儿子有通信站即可，但究竟是哪一个被点亮呢？那么讨论对儿...

本题翻译过来：在一棵书上每条边都必须有一个或多个士兵节点，求最少的士兵节点的个数。 那么对于每一个节点来说有选与不选两种情况：dp[i][0/1]; 如果选的话儿子节点选与不选都行：dp[i][1] = 1 + (儿子节点累加和)min(dp[u][0], dp[u][1]); 如果不选的话儿子节点就必须要选才行：dp[i][0] = (儿子节点累加和)dp[u][1]; //本题翻译过来：在一棵书上每条边都必须有一个或多个士兵节点，求最少的士兵节点的个数。 //那么对于每一个节点来说有选与不选两种情况：dp[i][0/1]; //如果选的话儿子节点选与不选都行：dp[i][1]&nb...

题目中的意思翻译过来其实是在一颗数上相邻的节点只能选择一个，那么最大的和为多少。 那么对于每一个节点来说就有选与不选两种状态：dp[i][0/1] 如果选的话那么以这个节点为根的子树最大和为：dp[i][1] = (f[i]+(所有子树和)dp[u][0]); 如果不选的话那么对于子树来说就有选与不选两种情况，两种情况选大的就行。：dp[i][0] = (所有子树和)max(dp[u][0], dp[u][1]); //题目中的意思翻译过来其实是在一颗数上相邻的节点只能选择一个，那么最大的和为多少。 //那么对于每一个节点来说就有选与不选两种状态：dp[i][0/1] //如果选的话那...

对于某个节点来说，如果该节点删除那么就会形成他儿子节点全部独立成一棵树和他父亲节点的那棵树。 那么状态转移方程：dp[i] = (total-f[i], (所有儿子节点最大的那个)f[u]) 对于求某个节点下有多少节点来说是一个简答树状dp问题。 f[i] = 1+(所有儿子节点)f[u]; //对于某个节点来说，如果该节点删除那么就会形成他儿子节点全部独立成一棵树和他父亲节点的那棵树。 //那么状态转移方程：dp[i] = (total-f[i], (所有儿子节点最大的那个)f[u]) //对于求某个节点下有多少节点来说是一个简答树状dp问题。 //f[...

本题得知道一个结论，如果序列里面的数的最大公约数为1的话就一定可以到达任意一个魔法阵。 那么就对最大公约数进行动态规划。以每个数为外层循环。每一次都与前面有的或产生的数进行最大公约数的计算，然后更新某个数作为最大公约数所需要的花费即可。 //对于某一个数 它的加入对原来产生的影响是原来拥有的所有的数的花费。 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn&nb...

本题直接使用dfs，然后配合剪枝去接最好。直接dfs的去进行每一步当递归到最大的拥有宝藏的岛屿的下一个就可以宣布结束返回了。 如何剪枝：本题中dfs是从前向后的传参形的记录当前的宝藏数量，那么如果某个岛屿第二遍被递归到的时候如果当前的宝藏数还没有之前的大。那么再递归下去就没有意义了。 这是我看别人的AC代码得出来的，但是我觉得这个剪枝有些问题，在这里面决定后面情况的不止是他当前在哪个岛屿还有当前到达这个岛屿跨越了多少，这个东西可以决定以后的步伐。所以单纯的用当前岛屿的最大宝藏数取判断总感觉有些问题。 我自己一开始写的是记忆化搜索，但是只过了80%就是因为记忆性剪枝的时候没考虑...

#include <bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 1e6+7; int stone[107], now[107]; int vis[maxn], dp[maxn]; int main() {     int l;  &n...

使用二进制运算去优化01背包的循环过程可以。 可以使用二进制去优化01背包的循环过程原因：在背包循环里面其实是针对于某一个物品判断如果他自身不取或者取能不能有一种是可以满足条件的。那么不取显而易见就是上一层循环的结果直接继承下来，取呢？取就得减去这个物品本身的重量，那么这个过程其实和序列整体左移是一样的效果。那么直接左移重量个位数，然后位或运算就可以实现这两个要求。 #include "bits/stdc++.h" #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(null...

求每个纵列的前缀和然后去遍历每个纵列。对于某一行来说可以使用在一维求最大序列和的做法，如果前一个最大总和小于0的话就直接取自身，如果大于0的话就加上。 #include <bits/stdc++.h> using namespace std; const int maxn = 100+10; int a[maxn][maxn]; int sum[maxn][maxn]; int main() {     int N...

从左向右看，对于i位置选出j个不相交连续字段，那么对于i位置来说就有两个选择： 首先要知道的是我们所确定的区间里面的j个不相交的连续字段必须以i所在的字段结尾（因为如果不以i所在的字段结尾的话那在前面一定有结尾的下标，那本身就不应该是i这个区间了。） dp[i][j] = dp[i-1][j]+a[i];//i拼到i-1所在的字段称为一体。 dp[i][j] = dp[k][j-1]+a[i];//i自成一个字段。那么前面到底以哪个下标结尾才能最大需要去遍历寻找。 所以最后的状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[k][j-1])+a[i]; 但是...

从题目中规律可以看出来在某个人要过河的时候要么是最快的那个人来接她，要么是还剩下两个让最快的把船开回来然后让这两个过去，之后让第二快的把船开过来，全部过去。这两个在题目中的样例里面都有体现。 dp[i] = max(dp[i-1]+a[0]+a[i], dp[i-2]+a[0]+a[i]+a[1]+a[1]); //dp[i] = max(dp[i-1]+a[0]+a[i], dp[i-2]+a[0]+a[i]+a[1]+a[1]); #include <bits/stdc++.h> using namespace&n...

//每次都要在每一层进行取，也就是说层与层之间没有什么关联。x,i和j是区间左右。 //dp[x][i][j] = max(dp[x][i+1][j]+pow(2,n)*a[i][j], dp[x][i][j-1]+pow(2,n)*a[i][j]); //每次都要在每一层进行取，也就是说层与层之间没有什么关联。x,i和j是区间左右。 //dp[x][i][j] = max(dp[x][i+1][j]+pow(2,n)*a[i][j], dp[x][i][j-1]+pow(2,n)*a[i][j]); #include <bits/stdc...