【做题笔记】动态规划专题（DP）

标签：ch int 笔记 子树 专题 DP 节点 dp getchar

这里记录笔者这几天做的有关于 dp 的题目。

树形 dp

#1 P1122 最大子树和

题目链接：https://www.luogu.com.cn/problem/P1122

题意：选出一个联通分量，使得联通分量的点的点权和最大。

思路：考虑以 \(f_i\) 表示以点 \(i\) 为根节点子树联通分量权值的最大值。

于是初始化有 \(f_i=a_i\)，因为他的子树不管断掉几个一定包含自己。

如果不是叶子节点，考虑如果它儿子（设为 \(j\)）的 \(f_j>0\)，则这个节点一定对 \(f_i\) 有贡献，加上它的子树会使得答案值更大，否则不选。

于是就有了递推方程：

\[f_i=\sum_{j \in \text{son}(i)} f_j \qquad \text{If } f_j>0 \]

code：

#include<bits/stdc++.h>
using namespace std;

const int N = 2e4 + 5;

inline int read() {
	int x(0),f(0);
	char ch=getchar();
	for(; !isdigit(ch); ch=getchar()) f|=(ch=='-');
	for(;  isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return f?-x:x;
}

int val[N],dp[N];
int n,m,ans=numeric_limits<int>::min();

struct graph {
	int to,nxt;
} G[N<<1];
int cnt,head[N];
void addEdge(int u,int v) {
	G[++cnt]= {v,head[u]};
	head[u]=cnt;
}

void dfs(int x,int fa) {
	dp[x]=val[x];
	for(int i=head[x]; i; i=G[i].nxt) {
		int t=G[i].to;
		if(t==fa) continue;
		dfs(t,x);
		if(dp[t]>0)
			dp[x]+=dp[t];
	}
}

int main() {
	n=read();
	for(int i=1; i<=n; i++) val[i]=read();
	for(int i=1; i<n; i++) {
		int u,v;
		u=read(), v=read();
		addEdge(u,v);
		addEdge(v,u);
	}
	dfs(1,-1);
	for(int i=1; i<=n; i++)
		ans=max(ans,dp[i]);
	printf("%d\n",ans);
}

标签：ch,int,笔记,子树,专题,DP,节点,dp,getchar
From： https://www.cnblogs.com/TheSky233/p/17043410.html