首页 > 其他分享 >洛谷 P6223

洛谷 P6223

时间:2022-10-25 21:33:51浏览次数:66  
标签:P6223 head 子树 洛谷 int siz void cnt

树形 DP 完全不会。。

首先将题目条件改一下:每个人有 \(x-v_i\) 块钱,要求使所有人的钱数非负的最小操作次数。

注意到对于节点 \(u\),在子树 \(u\) 内至多操作 \(siz_u-1\) 次。

所以可以设 \(f_{i,j}\) 表示在子树 \(i\) 内,操作 \(j\) 次,使得除节点 \(i\) 以外其余点均非负,节点 \(i\) 的可能权值的最大值。

转移就枚举当前 \(u\) 的操作次数 \(j\),它的儿子 \(v\) 的操作次数 \(k\)。

然后考虑子树 \(v\) 是否移到子树 \(u\) 上来,注意到若 \(f_{v,k}\ge0\) 的话是可以不转移的,否则一定得转移。

最终答案就是最小的 \(i\) 满足 \(f_{1,i}\ge 0\)。

时间复杂度 \(\mathcal O(n^2)\)。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 2005, inf = 0x3f3f3f3f;
int n, x;
int a[N];
int head[N], ver[N*2], nxt[N*2], cnt;
int f[N][N], tmp[N], siz[N];

void add(int u, int v) {
	ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}

void chkmax(int &a, int b) { if (a < b) a = b; }

void dfs(int u, int fa) {
	f[u][0] = a[u], siz[u] = 1;
	for (int i = head[u]; i; i = nxt[i]) {
		int v = ver[i];
		if (v == fa) continue;
		dfs(v, u);
		for (int j = 0; j <= siz[u] - 1 + siz[v]; ++j) tmp[j] = -inf;
		for (int j = 0; j <= siz[u] - 1; ++j)
			for (int k = 0; k <= siz[v] - 1; ++k) {
				chkmax(tmp[j + k + 1], f[u][j] + f[v][k]);
				if (f[v][k] >= 0) chkmax(tmp[j + k], f[u][j]);
			}
		siz[u] += siz[v];
		for (int j = 0; j <= siz[u] - 1; ++j) f[u][j] = tmp[j];
	}
}

int main() {
	scanf("%d%d", &n, &x);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] = x - a[i];
	for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), add(u, v), add(v, u);
	dfs(1, 0);
	for (int i = 0; i < n; ++i) if (f[1][i] >= 0) return printf("%d", i), 0;
	return 0;
}

标签:P6223,head,子树,洛谷,int,siz,void,cnt
From: https://www.cnblogs.com/Kobe303/p/16826398.html

相关文章

  • 洛谷 P5698 [CTSC1998]算法复杂度 题解
    前言咕了大半年,我回来了说实话当鸽子的感觉挺不错???原题链接题意给定一个伪代码,判断他总共需要进行几次操作,用多项式形式输出。题解首先,这是一道模拟题,发现性质的话比......
  • 洛谷 P3401
    甚么神仙题啊……#include<iostream>#include<vector>#include<cstdio>#include<cstring>#include<iterator>#include<utility>#defineintlonglongusin......
  • 洛谷上扒的DP练习题
    DP综述最优子结构:把原问题化到规模更小的问题后,原问题的最优解一定能从规模更小问题的最优解推出。无后效性:如果在某个阶段上过程的状态已知,则从此阶段以后过程的发展变......
  • 洛谷 P8089
    考虑对于满二叉树,显然只与\(dep\)有关,设\(f_{i}\)表示深度为\(i\)的答案(确切的说应该是到最深深度的距离),则有\(f_1=1,f_i=(f_{i-1}+1)^2(i\ge2)\)。则对于完全二叉......
  • 洛谷P5020题解
    原题P5020[NOIP2018提高组]货币系统思路概述题意分析给定包含一个整数\(n\)和一个正整数集合\(a\)的货币系统\((n,a)\),要求将其化简,输出最简的货币系统中的面......
  • 洛谷P2827题解
    原题P2827[NOIP2016提高组]蚯蚓思路概述题意分析给定整数\(n,m,q,u,v,t\)和一个数列\(\{a\}\),进行\(m\)次操作如下:每次选取其中最大数\(x\)切分为\([px],x......
  • 「题解」洛谷 P8529 [Ynoi2003] 赫露艾斯塔
    构造半平面莫队?/jk注意到对于一个半平面的直线,通过平移和旋转经过的点数,一定大于等于它们的对称差,因为对称差中的点会被经过奇数次,不在对称差中的点会被经过偶数次。那么......
  • 洛谷 P3224 [HNOI2012]永无乡 题解
    查询第\(k\)小值想到权值线段树。合并操作想到线段树合并。维护连通性想到并查集。并查集合并方向应与线段树合并方向一致。查询时,先求出并查集的根再在线段树上询......
  • 洛谷P8060 [POI2003] Sums
    题目链接题意给定序列\(a_1,a_2,\cdots,a_n\),将其划分为若干段,要求子段和单调不增,求最大段数。数据范围:\(1\len\le10^5,1\lea_i\le10^4\)。题解考虑逆推。问题......
  • 洛谷P1928 外星密码
    一波小解释本人第一次写博客,单纯是为了记录,可能只有自己能看懂哈哈,第一次语法格式什么的还把握不好希望谅解。外星密码题目描述有了防护伞,并不能完全避免2012的灾难......