P1717 钓鱼

题目描述

话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽，为了表示安慰和鼓励，VIP999 决定请他吃一次“年年大丰收”，为了表示诚意，他还决定亲自去钓鱼。

但是，因为还要准备 NOIP2013, z老师只给了他 H 个小时的空余时间，假设有 n* 个鱼塘都在一条水平路边，从左边到右编号为 1, 2, 3 .. n 。

VIP是个很讲究效率的孩子，他希望用这些时间钓到尽量多的鱼。他从湖1出发，向右走，有选择的在一些湖边停留一定的时间钓鱼，最后在某一个湖边结束钓鱼。他测出从第 i 个湖到 i+1个湖需要走 5×t_i* 分钟的路，还测出在第 i 个湖边停留，第一个5分钟可以钓到鱼 f_i，以后再每钓5分钟鱼，鱼量减少 d_i。为了简化问题，他假定没有其他人钓鱼，也不会有其他因素影响他钓到期望数量的鱼。请编程求出能钓最多鱼的数量。

输入格式

第一行：湖的数量n。

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

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

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

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

输出格式

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

输入输出样例

输入 #1

1
2
3
4
5
2
1
10  1
2  5
2

输出 #1

1
31

dp: $d[i][j]$ 表示前 i 个鱼塘花费 j 时间的最大收获。

$dp[i][j] = max(dp[i][j] ,dp[i-1][j - k - t[i-1]] + kf[i] - k(k-1)/2 * d[i]);$

贪心： 直觉上，应该选择单位时间收获最大的鱼塘 x 先钓鱼，等到单位时间收获变小时，再考虑其他鱼塘。但是鱼塘之间转移有额外的代价。如果鱼塘 x 在最末尾，光是到达 x 就要花费很大的代价，显然这样贪心是不行的。如果，末尾是固定的呢？就是说花费在路程上的时间是固定（走回头路显然不合理），问题就转化为，n 个鱼塘，每个鱼塘每分钟的产鱼量递减，求 h 分钟内的最大产量，这样，只要选每分钟最大产量那个鱼塘。这样又有一个问题：如果每分钟最大产量的那个鱼塘都不同，就要来回转移。这里要用到一个“瞬移”的技巧 ，因为每个鱼塘的产鱼量是连续递减，所以这是可行的。最后呈现的效果就是，在一个鱼塘连续钓 t 分钟，然后再去往下一个鱼塘。

具体就是： 枚举最末尾的鱼塘，减去路程，剩余时间 h’ , 用优先队列维护每分钟最大产量，花光 h’ 为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int MAX=25+10;
int n,h,cnt,ans;
int f[MAX],d[MAX],t[MAX],tt[MAX],dp[MAX][200];
int main(){
	freopen("in","r",stdin);
	sf(n);sf(h);
	h = h * 60 /5;
	fi(i,1,n+1) sf(f[i]);
	fi(i,1,n+1) sf(d[i]);
	fi(i,1,n) sf(t[i]);
	fi(i,1,n+1){ //到达i点至少需要的时间 
		tt[i] = tt[i-1] + t[i-1];
	}
	fi(i,1,n+1)
		fi(j,tt[i],h+1)
			fi(k,0,j-t[i-1]+1) if( j - k - t[i-1]>=0 && (k-1)*d[i]<f[i]){
				dp[i][j] = max(dp[i][j] ,dp[i-1][j - k - t[i-1]] + k*f[i] - k*(k-1)/2 * d[i]);
				ans = max(ans,dp[i][j]);
			}
	pf(ans);
	return 0;
}