威风镰鼬

题解

/ 注册

全部文章 / 题解（共4篇）

题解 | #骑士#

思路图可能会有多个连通块，整个图最多有一个环。基环树的题目，对每一块找环切断，然后树形dp。环的切断方式有两种，从那条边的起始点出发做两次dp，当前块的答案就加上两次dp结果的较大值。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f...

树形dp 基环树

2021-10-19

1 367

题解 | #xinjun与阴阳师#

思路对于每个选择的点，其周围的点都是不能选的，我们从根结点出发深搜+DP，就能求出答案了。可以参考没有上司的舞会，这道题就是退化版。代码 #include<bits/stdc++.h> using namespace std; const int maxn=500005; str...

dfs 树形dp 搜索动态规划 2星

2021-07-06

0 443

题解 | #没有上司的舞会#

思路树形dp基础题型，dp[i][0]表示i不选中时的最大快乐指数，dp[i][1]表示i选中时的最大快乐指数，所以我们只要先找到一个根节点，然后向下dfs，dp[root][0]和dp[root][1]的较大值就是答案。从下往上状态转移，我们先搜索到叶子节点，然后求出父节点的dp[i][0]和d...

dfs 树普及组图论树形dp

2021-06-16

1 430

题解 | #树上子链#

思路对于一个起始点x，最大子链是从x开始或者从x的子节点开始的最大子链。答案是从x作为起始点得到的最大子链的最大值，起点在dfs过程中走一遍就不会超时了。然后就是树形dp的问题啦。坑点:要开ll，同时注意所有点权值都为负数的情况。代码 #include<bits/stdc++.h> ...

dfs 树图论树形dp

2021-06-16

1 481