树形dp求助
  • 板块学术版
  • 楼主WD2c0mP
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/2/21 20:14
  • 上次更新2023/10/24 00:09:28
查看原帖
树形dp求助
780641
WD2c0mP楼主2023/2/21 20:14

P2015这题,我看深进上的代码差不多是这样的

#include<bits/stdc++.h>
using namespace std;
int dp[110][110],s[110][2],siz[110],val[110][2];
int n,q;
void dfs(int u) {
	int x = s[u][0],y = s[u][1];
	if (!x && !y) return ;
	dfs(x);dfs(y);
	siz[u] = siz[x] + siz[y] + 2;
	for (int i = -1;i <= siz[x];i ++) {
		for (int j = -1;j <= siz[y];j ++) {
			int vl = i == -1 ? 0 : dp[x][i] + val[u][0];
			int vr = j == -1 ? 0 : dp[y][i] + val[u][1];
			if (vl + vr > dp[u][i + j + 2]) 
				dp[u][i + j + 2] = vl + vr;
			else dp[u][i + j + 2] = 0;
		}
	}
}
int main(){
	cin >> n >> q;
	for (int i = 1;i < n;i ++) {
		int x;
		cin >> x;
		int b = s[x][0] > 0;
		cin >> s[x][b] >> val[x][b];
	}	
	dfs(1);
	cout << dp[1][q] << endl;
	return 0;
}

请问这里siz数组的含义是什么?

2023/2/21 20:14
加载中...