本文主要是介绍航电 1011 树形DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
树形DP
题目：有一个树形的山洞，每个洞有存在bug，经过时，需要留下trooper来战斗，trooper不能往回走。每个trooper能消灭20个bug，给定trooper数量，求能获得brain的最大概率。
由题意知，若要经过子节点，必须经过父节点。
定义dp[i][j]表示用j个trooper来占领已i为根节点的子树的概率最大值。
递归的定义dp[i][j]= max{dp[i][j-k]+dp[v][k],dp[i][j]};
用j个trooper来占领根节点为i的子树可能的取值时用k个trooper来占领根节点为v[i的子节点]的子树加上已(j-k)来占领i之和。
前提是j要大于cost[i]，因为占领v[i的子节点]，必须经过i,所以必须花费cost[i]个trooper。
k表示用来占领根节点为v的子树分配的trooper数量,k<=j-cost[i](原因同上)，再加上剩下j-k位trooper的最大概率。
再与dp[i][j]比较取较大值。
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;//AC
public class Main_1011 {//dp[0-n][1-m]static int[][] dp;static int[] cost;static int[] brain;static ArrayList<Integer>[] adj;static int m;public static void main(String[] args) throws FileNotFou这篇关于航电 1011 树形DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
