pascal 求助,懂得来

来源:百度知道 编辑:UC知道 时间:2024/06/02 16:34:37
题是这样的:
钓鱼(Fish)

【问题描述】
约翰是个垂钓谜,星期天他决定外出钓鱼h小时(1≤h≤16),约翰家附近共有n个池塘(2≤n≤25),这些池塘分布在一条直线上,约翰将这些池塘按离家的距离编上号,依次为L1,L2,…,Ln,约翰家门外就是第一个池塘,所以他到第一个池塘是不用花时间的,约翰可以任选若干个池塘垂钓,并且在每个池塘他都可以呆上任意长的时间,但呆的时间必须为5分钟的倍数,(5分钟为一个单位时间),已知从池塘Li到池塘Li+1要化去约翰ti个单位时间,每个池塘的上鱼率预先也是已知的,池塘Li在第一个单位时间内能钓到的鱼为Fi(0≤Fi≤100),并且一个常数di(0≤di≤100),现在请你编一个程序计算约翰最多能钓到多少鱼。
每过一个单位时间在单位时间内能钓到的鱼将减少
【输入文件】
输入文件第一行为一个整数n,第二行为一个整数h,第三行为n个用空格隔开的整数,表示Fi(i=1,2,…,n),第四行为n个用空格隔开的整数,表示di(i=1,2,…,n),第五行为n-1个用空格隔开的整数,表示ti(i=1,2,…,n-1)

【输出文件】
输出一个整数,表示约翰最多能钓到的鱼的数量。

【输入输出样例】
输入:
2
1
10 1
2 5
2

输出:
31

我觉得是Dp,但是方程没弄明白
我这么写的,得数不对
program fish;
var i,j,k,n,h,h1,tot,bj:integer;
f,d,t:array[1..200] of integer;
g:array[-10..400,1..50,-10..400] of longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a
else max:=b;
end;
begin
readln(n);
readln(h1);

黑书(《算法艺术与信息学竞赛》)的贪心法讲解中的原题
既然有贪心他,那就没必要dp了,而且贪心时间复杂度(kn*n),用堆的话(knlogn),你的三层dp已经超过这个复杂度了
参见黑书p13
他只是思路,那本书上很少有标程,大多都是思路或者伪代码,如果你想搞竞赛的话严重建议你去买一本并做完(尽可能)上面的例题和练习,很有好处。
http://58.251.57.206/down1?cid=DFC3B13CCBD6536D2F49FCDFBD8D50A42E989925&t=3&fmt=&usrinput=算法艺术与信息学竞赛&dt=1002004
迅雷的下载链接,为pdf,或者自己搜也行