本文主要是介绍hihocoder#1055 : 刷油漆 算法详解以及java源码实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题地址详见：http://hihocoder.com/problemset/problem/1055?sid=869767
题目分析：简而言之，就是获得一棵树如果涂连续节点，节点数目一定，最终获得的最大值是多少。
思路：
dp[u][j]表示以节点u为根的大小为 j 的树可得到的最大分数，答案就是dp[1][m]。
状态转移方程为：dp[u][j]=max(dp[v1][k1]+dp[v2][k2]+...+dp[vx][kx])，v是u的子节点。
注意点：
1.边是单向的还是双向的：因为要求是从1开始，我们可以把树设置为单向边，按照节点从大向小的顺序，避免重复遍历，陷入死循环。还有一种递归是根据边来递归的，参考http://www.cnblogs.com/easonliu/p/4468799.html
2.M是正向还是反向遍历？考虑到我们背包问题，物品不可重复使用，类似于这里的节点不可重复使用，我们采用的是用上一状态更新当前状态，而不是更新后的状态更新当前状态，所以选择反向遍历。
源代码如下：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class CrushRoller {public static void main(String args[]){Scanner in=new Scanner(System.in);while(in.hasNextInt()){int N=in.nextInt();int M=in.nextInt();//存储每个节点的价值int[] V=new int[N+1];//dp[i][j]表示存储i节点为根的时候，涂上M个子节点的最大价值int[][] dp=new int[N+1][M+1];//存储单向边List<List<Integer>> map=new ArrayList<List<Integer>>();map.add(new ArrayList<Integer>());for(int i=1;i<=N;i++){V[i]=in.nextInt();map.add(new ArrayList<Integer>());dp[i][1]=V[i];}for(int i=1;i<N;i++){int a=in.nextInt();int b=in.nextInt();map.get(a).add(b);}dfs(dp,1,M,map);System.out.println(dp[1][M]);}in.close();}public static void dfs(int[][] dp,int node,int M,List<List<Integer>> map){List<Integer> children=map.get(node);//递归调用子树获得子树的dpfor(int child:children){//获得以当前为根的子树的最大dpdfs(dp,child,M-1,map);//类似背包问题从大到小for(int i=M;i>1;i--){for(int j=1;j<i;j++){dp[node][i]=Math.max(dp[node][i],dp[node][i-j]+dp[child][j]);}}}}
}
这篇关于hihocoder#1055 : 刷油漆 算法详解以及java源码实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
