本文主要是介绍算法训练 采果子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Lyl大牛今天心情不错，于是走到埃及郊外旅游(会不会碰到MMY?...PS:MMY的含义请自行理解)。他边走边向四周望望，发现周围有许多果树。这些树之间互相到达的时间Lyl是知道的（假定每两棵树之间都拥有独立的边可以到达）。他数出了这些果树上果子的个数，并且估了估每个的价格（真是个奇怪的人）。Lyl规定了一种采摘方案，就是对于第i棵树来说，它有a[i]个果子，且所有果子价值为s[i]，摘取时间为c[i](小时)。并且，当他摘了第i个树上的果子后，后面他所选择去摘的果树上的果子数必须大于第i棵树上的果子数目，说白了就是一个上升序列；并且每到一棵树，他都必须摘下该树上的所有果子。一开始，Lyl可以在任意一棵树，他只有m小时，那么，在他所拥有的限定时间内，他想知道，这样摘取的最大价值是多少？
输入格式
输入文件tree.in第一行2个数：n（表示这条路上的大树数），m（总共时间）
接下来第n+1行，每行三个数a[i],s[i],c[i] (第i+1行输入的为第i颗果树的信息)
且保证有1<=a[i]<=2^31-1;1<=s[1]+s[2]+…+s[n]<=2^31-1;s[i]>=0; 1<=c[i]<=100
接下来的n行，每行n个数，第i行第j个数表示从树i到树j的时间。（0<=T[I,j]<=100;）
输出格式
输出文件tree.out有且仅有一个数，即按这样方法摘取的最大价值。
样例输入
4 10
1 10 2
2 5 3
3 6 1
4 9 4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0
样例输出
21
（先摘第1棵树上的，再摘第2棵树上的，然后第3棵树上的）
数据规模和约定
对于60%的数据 ,1<=N<=60,1<=m<=100;
对于100%的数据 ,1<=N<=100, 1<=m<=1000.
import java.util.Scanner;public class Main {static Tree[] tree = new Tree[110];//树的相关信息static int[][] Cross = new int[110][110];//Cross[i][j] 树i到树j所用的时间static int n,m;static int maxV=0;//最大价值static int[][] Dp = new int[110][1010];//public static void main(String[] args) {Scanner sc = new Scanner(System.in);//1.输入相关的数据n = sc.nextInt();//树的个数m = sc.nextInt();//可以采摘的总时间tree[0] = new Tree(0,0,0,0);for(int i=1;i<=n;i++){tree[i] = new Tree();tree[i].id = i;tree[i].count = sc.nextInt();tree[i].value = sc.nextInt();tree[i].cost = sc.nextInt();}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){Cross[i][j] = sc.nextInt();}}//2.按照果子数目递减的顺序，排列树(冒泡排序)boolean flag;for(int i=n;i>0;i--){flag = false;for(int j=1;j<i;j++){if(tree[j].count<tree[j+1].count){Tree temp = tree[j];tree[j] = tree[j+1];tree[j+1] = temp;flag = true;}}if(flag == false) break; //没有进行交换}//3.找出最大值for(int i=1;i<=n;i++){for(int j=0;j<i;j++){//此时j的果子数目>=i的果子数目if(tree[i].count == tree[j].count) continue; //树i和树j的果子数目一样，跳过本次循环int tval = tree[i].value;//树i的总价值int tcost = tree[i].cost+Cross[tree[i].id][tree[j].id];//树i的总代价+从树i到树j的总代价for(int o=m-tcost;o>=0;o--){//o:表示当前剩下可用的时间Dp[i][o]=Math.max(Dp[i][o], Dp[j][o+tcost]+tval);maxV = Math.max(maxV,Dp[i][o]);}}}//for//5.输出最大的价值System.out.println(maxV);}}
//1.表示树的相关信息
class Tree{int id;//树的编号int count,value,cost;//果子数、该树的总价值、摘果子用的时间public Tree(){}public Tree(int id, int count, int value, int cost) {super();this.id = id;this.count = count;this.value = value;this.cost = cost;}}
这篇关于算法训练 采果子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
