P1717 钓鱼

题目描述

话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽，为了表示安慰和鼓励，VIP999决定请他吃一次“年年大丰收”，为了表示诚意，他还决定亲自去钓鱼，但是，因为还要准备2013NOIP,z老师只给了他H（1<=H<=16）个小时的空余时间，假设有N（2<=n<=25）个鱼塘都在一条水平路边，从左边到右编号为1、2、3、。。。、n）。VIP是个很讲究效率的孩子，他希望用这些时间钓到尽量多的鱼。他从湖1出发，向右走，有选择的在一些湖边停留一定的时间钓鱼，最后在某一个湖边结束钓鱼。他测出从第I个湖到I+1个湖需要走5*ti分钟的路，还测出在第I个湖边停留，第一个5分钟可以钓到鱼fi，以后再每钓5分钟鱼，鱼量减少di。为了简化问题，他假定没有其他人钓鱼，也不会有其他因素影响他钓到期望数量的鱼。请编程求出能钓最多鱼的数量。

输入输出格式

第一行：湖的数量n。

第二行：时间h（小时）。

第三行：n个数，f1，f2，…fn。

第四行：n个数，d1，d2，….dn。

第五行：n-1个数，t1，t2，….tn-1

一个数，所能钓鱼的最大数量。

输入输出样例

输入样例#1：

2
1
10  1
2  5
2

输出样例#1：

Solution：

本题可以贪心，这里我用的是$DP$。

设$DP[i][j]$表示在第$i$个鱼池耗费了$j$的时间能获得的最多鱼的个数。

当在$i$鱼池耗费$k$个单位$5$的时间，能捕捉到的鱼个数为：

$\sum (f[i]-(k-1)*d[i])=\sum f[i]-\sum (k-1)*d[i]$

则容易得到状态转移方程：

$DP[i][j]=max(DP[i][j],DP[i-1][j-k-t[i-1]+frac{f[i]*k-k*(k-1)*d[i]}{2})$