最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

每日视讯:P1352 没有上司的舞会+P1122 最大子树和(树形DP入门)

来源:博客园

前言

今日偶然打开 \(oi-wiki\),发现树形 \(DP\) 例题正好是之前在洛谷上鸽着的一道题。所以......


(资料图)

\(\color{red}{很高兴以这样的方式认识你,树形 DP !}\)

这例题造的太好了,简直是无痛入门(感动.jpg)

P1352 没有上司的舞会

题目传送门~

思路剖析

状态定义

\(dp_i\) 表示的是以 \(i\) 为根节点的子树所获得的最大价值。

由于每个节点代表着一位人物,有来与不来两种状态,所以再加一维状态变量。

\(dp_{i,0}\) 表示以 \(i\) 为根节点的子树所能获得的最大价值,且这位人物没来。 \(dp_{i,1}\) 则对应来了的状态。

状态转移方程

现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 r_i。 但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。

根据题意描述,容易得出状态转移方程:

\(dp_{i,0} += max (dp_{j,0},dp_{j,1})\)

\(dp_{i,1} += dp_{j,0}\)

\(j\) 指的是 \(i\) 的子节点,且显然 \(dp_{i,1}\) 的初始值为 \(r_i\)。

code

点击查看代码
#include#include#includeusing namespace std;int n,a[6005];int head[6005],nex[6005],edge[6005],tot;int vis[6005],dp[6005][2];void dfs(int x){dp[x][1]=a[x];for(int i=head[x];i;i=nex[i]){int y=edge[i];dfs(y);dp[x][1]+=dp[y][0];dp[x][0]+=max(dp[y][0],dp[y][1]);}return;} int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i

P1122 最大子树和

题目传送门~

思路剖析

谁是根节点

由于这题是无向图(但由于以 \(n-1\) 条边相连接,所以本质与树并无太大区别),所以要讨论以谁作为根节点。

根节点之所以重要,是因为在递归过程中,我们已经默认根节点所代表的那束花已经被保留了,但根节点代表的花不一定在最优解的集合之中。

仔细模拟后,不难发现,对于以 \(i\) 为根节点的子树,\(dp_i\) 往下为最优解,而往上由于还未更新,因此相当于剪去 \(dp_i\) 与其根节点的枝桠。

进一步推理,无论通过哪个节点作为根节点,再递归的过程中,其实已经变相枚举了将其剪去的种种情况,所以,只需要在过程中取最优解即可。

状态定义+状态转移方程

这点比较好理解,所以合并在一起阐述。

\(dp_i\) 表示以 \(i\) 为根节点的子树所获得的最大美丽值。

显然有

\(dp_i+=max(dp_j,0)\)。

\(j\) 为子节点,当其所带来的价值为负数时,不如直接剪掉。

code

有几处雷点在注释中标记出来了(都是血泪教训啊QAQ)

点击查看代码
#include#include#includeusing namespace std;int n,ans=-0x3f3f3f3f;//答案可能为负!要初始化为负无穷int head[16005],nex[35005],edge[35005],tot;//由于是双向边,所以空间要开双倍int dp[16005],vis[16005];void dfs(int x){vis[x]=1;//不要在循环内标记,否则标记不到根节点本身。for(int i=head[x];i;i=nex[i]){int y=edge[i];if(vis[y]) continue;dfs(y);if(dp[y]<=0) continue;dp[x]+=dp[y]; }ans=max(ans,dp[x]);return;} void add(int l,int k) {nex[++tot]=head[k],head[k]=tot,edge[tot]=l;}int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&dp[i]);for(int i=1;i

第 \(7、8\) 道,(‾◡◝)。

加油!

关键词: 转移方程 点击查看