dp

树形dp

4.25

1：NC15033小G有一个大树

• 题意：找树的一个节点使得他的最大子树最小
• 思路：

状态：f[i]:将点i删掉以后最大连通块的大小
状态转移方程：f[i]=max(n-tot[i],max(tot[k]))
             k是i的儿子
             tot[i]是以i为根的子树的大小

2:NC51178没有上司的舞会（最大独立集）

• 题意：没有人愿意和上司一起参加，每个人有快乐指数，求快乐指数综合最大
• 思路：

状态：i选或者不选会影响子树的结果
f[i][0]表示不选择i点时最大的快乐指数，f[i][1]表示选i点
状态转移方程：f[i][0]=∑(max(f[j][0],f[j][1])
             f[i][1]=hi+∑f[j][0]
			 边界：f[i][0]=0,f[i][1]=hi--i是叶节点
             结果为max(f[root][0],f[root][1])
​
 
​
 

3：旅游（https://ac.nowcoder.com/acm/contest/81481/1001）与2同类

4：poj1463 NC106060 Strategic game（树的最小点覆盖）

• 题意：城堡的所有道路形成一个n个节点的树，如果在一个节点上放上一个士兵，那么和这个节点相连的边就会被看守注，问把所有便看守住最少需要放多少士兵。
• 思想

状态：f[x][1]在x放士兵，以x为根的子树全部被看守住的最少所需的士兵数目
	  f[x][0]在x不放士兵~
状态转移方程：f[x][1]=1+∑min(f[i][0],f[i][1])//他的儿子可放可不放
	  f[x][0]=∑f[i][1]//他的儿子必须放
结果为min(f[root][0],f[root][1]

5:NC24953 Cell Phone Network(树的最小支配集） 题意：给你一颗无向树，问你最少用多少个点可以覆盖掉所有其他的点。一个点被盖，他自己和与他相邻的点都算被覆盖）

• tips：将父亲、自己、儿子都可以考虑放到状态里面去，你要什么就放什么

4.30

• 题意

• 思想

状态：f[u][j]表示在以u为根的子树保留j个分支可以得到的最大苹果数量
状态转移方程：f[u][j]=f[l][j-1]+a[j][l]
或=f[r][j-1]+a[j][r]
或=f[l][x]+f[r][j-2-x]+a[j][l]+a[j][r]


如果是多叉树 树上背包，左森林当成左子树，右森林当成右子树，当作二叉树处理
F[u][j]=max(f[u][k]+f[v][j-k+1]+w)
v分别是u的儿子，w为u到v边上的苹果数目，k属于[0,j]

2：树的直径，记录路径 做法1 两遍dfs 做法2 dp

3：

• 题意
• 思想

变形：

• 题意
• 思路 二分答案

状压dp

1：引入

• 题意
• 答案

变化

• 题意
• 思路 2：
• 题意（基于连通性的状压dp）
• 思路（注意位运算的优先级！加括号）

状态：f[i][j][k]表示第i行的状态为k，且已经放了j个国王的方案数
状态转移方程：f[i][j][k]+=f[i-1][j-num[k]][p]  ((k&p)==0,(x&(p<<1))==0(x&(p>>1))==0
且k和p都合法
（num[k]表示k状态的国王数）