树形dp – Tgotp-Blog

T16635 树集

考试中沙茶的没写出来TAT。

其实很水辣,考虑选出的区间最小与区间最大不能超过d/

固定区间最小,o(n)寻求答案,加起来就好了。

上午卡死在相同权值两点如何去重上面,其实就加一个判断,编号小的才能去统计编号大的的答案就ok了。

c++代码如下:
[crayon-5a633[……]

Read more

4013: [HNOI2015]实验比较

题意描述里有一句:“对每张图片 i,小 D 都最多只记住了某一张质量不比 i 差的另一张图片 Ki。”

即只有一个父亲,且m <= n,所以建树,容易想到树形dp,

对于 ”=“ 的,直接用并查集将之看成一个点,

对于“<”的,将小的连一条到大的点的边,

然后不一[……]

Read more

T15683 切

题目背景

2017/11/01 T1

题目描述

给出一棵有n个结点的树,将其中的一些边切掉,使得每个节点至少有k个结点与之相连(包括自己),求方案数对786433取模的结果。

输入输出格式

输入格式:

输入第一行,包含两个正整数n,k。

接下来的 n-1 行,每行包含两个正整数[……]

Read more

1040: [ZJOI2008]骑士

额,第一次做基环树的题,套路就是把换拆成链,然后只用拆的边所连的两点dp[0][i]取max

c++代码如下:

 

P2016 战略游戏

MDZZ,竟然是有向图,

很简单的树形dp,

令f[i][0]表示i点不放士兵,f[i][1]表示i点放士兵。

然后

f[x][1] += min(f[to[i]][0],f[to[i]][1]);

f[x][0] += f[to[i]][1];

搞定

c+[……]

Read more

C. Helga Hufflepuff’s Cup

C. Helga Hufflepuff’s Cup
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard out[……]

Read more

HDU6201 transaction transaction transaction

树形dp.

对于每个点求个最大最小值,比较一下,搞定了。

c++代码如下:

 

Apple Tree

 

Wshxzt is a lovely girl. She likes apple very much. One day HX takes her to an apple tree. There are N nodes in the tree. Each node has an amo[……]

Read more

士兵守卫

士兵守卫
soldier.cpp/c/pas
1s / 128M
【题目描述】
小明正在玩一款战略游戏,他所在地图有N个城市,这N个城市和城市之间的道路正好构
成一颗树,现在他需要在城市上放置士兵来守卫连接该城市的道路,你的任务是帮助他找到
用最少的方式士兵守卫所有道路的方案。
例如右[……]

Read more

P2014 选课

根本不会   太弱了,这题想了半天,自己参考打的贼慢,最后看了一下这一份。