UC知道求高人帮我解决下这题pascal难题，在线等！
来源：百度知道 编辑：UC知道 时间：2024/05/31 22:43:37
题4 采果子（fruit.pas）
【问题描述】
Zzq今天心情不错，于是走到郊外旅游。他边走边向四周望望，发现周围有许多果树。Zzq数出了这些果树上果子的个数，并且估了估每个的价格（真是个奇怪的人）。Zzq规定了一种采摘方案，就是对于第i棵树来说，它有a[i]个果子，且每个果子价格为s[i]，摘取时间为c[i]。那么，当你摘了第i个树上的果子后，后面你所选择去摘的果树上的果子数必须大于第i棵树上的果子数目，说白了就是一个上升序列,而且他不可以往回走。他只有k小时，那么，在zzq所拥有的限定时间内，他想知道，这样摘取得最大值是多少？
【输入格式】
第一行2个数：n（表示这条路上的大树数），k（总共时间）
接下来第n+1行，每行三个数：
a[i]（每棵树上的果子）,s[i]（这棵树上的所有果子的价格），c[i]（在每棵树上花费的时间）
【输出格式】
一个数，按这样方法摘取的最大值：m
【样例输入】
4 3
2 2 1
2 3 2
1 7 1
4 6 2
【样例输出】
13
（先摘第3棵树上的，再摘第4棵树上的）
【数据范围】
N,k<=10000; a[i],s[i]<=maxint;
废话谁不知道DP。。。就是求个解题方法啊
【问题描述】
Zzq今天心情不错，于是走到郊外旅游。他边走边向四周望望，发现周围有许多果树。Zzq数出了这些果树上果子的个数，并且估了估每个的价格（真是个奇怪的人）。Zzq规定了一种采摘方案，就是对于第i棵树来说，它有a[i]个果子，且每个果子价格为s[i]，摘取时间为c[i]。那么，当你摘了第i个树上的果子后，后面你所选择去摘的果树上的果子数必须大于第i棵树上的果子数目，说白了就是一个上升序列,而且他不可以往回走。他只有k小时，那么，在zzq所拥有的限定时间内，他想知道，这样摘取得最大值是多少？
【输入格式】
第一行2个数：n（表示这条路上的大树数），k（总共时间）
接下来第n+1行，每行三个数：
a[i]（每棵树上的果子）,s[i]（这棵树上的所有果子的价格），c[i]（在每棵树上花费的时间）
【输出格式】
一个数，按这样方法摘取的最大值：m
【样例输入】
4 3
2 2 1
2 3 2
1 7 1
4 6 2
【样例输出】
13
（先摘第3棵树上的，再摘第4棵树上的）
【数据范围】
N,k<=10000; a[i],s[i]<=maxint;
废话谁不知道DP。。。就是求个解题方法啊
DP
我直接想到的是dp:f[i,j,k],i:当前物品，j:所用时间，k:最优一棵树的果数
10000*10000*37000............
找个大牛问一下单调队列吧，我不懂了,囧.......
求高人帮我解决下这题pascal难题，在线等！
悬赏分：0 - 离问题结束还有 2 天 16 小时
题4 采果子（fruit.pas）
【问题描述】
Zzq今天心情不错，于是走到郊外旅游。他边走边向四周望望，发现周围有许多果树。Zzq数出了这些果树上果子的个数，并且估了估每个的价格（真是个奇怪的人）。Zzq规定了一种采摘方案，就是对于第i棵树来说，它有a[i]个果子，且每个果子价格为s[i]，摘取时间为c[i]。那么，当你摘了第i个树上的果子后，后面你所选择去摘的果树上的果子数必须大于第i棵树上的果子数目，说白了就是一个上升序列,而且他不可以往回走。他只有k小时，那么，在zzq所拥有的限定时间内，他想知道，这样摘取得最大值是多少？
【输入格式】
第一行2个数：n（表示这条路上的大树数），k（总共时间）
接下来第n+1行，每行三个数：
a[i]（每棵树上的果子）,s[i]（这棵树上的所有果子的价格），c[i]（在每棵树上花费的时间）
【输出格式】
一个数，按这样方法摘取的最大值：m
【样例输入】
4 3
2 2 1
2 3 2
1 7 1
4 6 2
【样例输出】
13
（先摘第3棵树上的，再摘第4棵树上的）
【数据范围】
N,k<=10000; a[i],s[i]<=maxint;
问题补充：废话谁不知道DP。。。就是求个解题方法啊