1046: 钓鱼(数据增强版)
Time Limit: 1 Sec Memory Limit:
128 MB
Submit: 11 Solved: 3
[][Status][Web Board]
Description
在一条水平路边。有n个钓鱼湖。从右到左编号为1、2、3……、n。
佳佳有H个小时的空余时间。他希望用这些时间尽可能多的钓鱼。他从湖1出发，向右走。有选择的在一些湖边停留一定时间钓鱼。最后在某一湖边结束钓鱼。佳佳測出从第i个湖到第i+1个湖须要走Ti分钟的路，还測出在第i个湖边停留，第一个5分钟能够钓到鱼Fi，以后再每钓5分钟鱼，鱼量降低Di。
若时间不足5分钟则无法完毕钓鱼。为了简化问题。佳佳假定没有其它人钓鱼，也不会有其它影响因素影响他钓到期望数量的鱼。请编程求出能钓最多鱼的方案。
Input
包括多组測试例子。以文件尾为结束。
第一行输入两个整数。n(2<=n<=1000)和时间 H（1<=H<=30）
第二行输入n-1个整数，T1、T2、……、Tn-1. (0<=Ti<=1000)
第三行输入n个整数，F1、F2、……、Fn. (0<=Fi<=1000)
第四行输入n个整数。D1、D2、……、Dn. (0<=Di<=1000)
Output
输出最大的钓鱼数量，每一个输出占一行
Sample Input
3 1
40 10
70 70 70
5 5 5
3 1
20 20
100 50 70
50 20 30
Sample Output
510
270
HINT
例子一：在湖1钓鱼60分钟。70+65+……+15=510
例子二：在湖1钓鱼10分钟。0+100+50=150
前往湖2花费20分钟。
在湖2钓鱼5分钟。150+50=200
前往湖3花费20分钟。
在湖3钓鱼5分钟。200+70=270
Source
解析：同POJ 1042 Gone Fishing （贪心）（刘汝佳黑书）
但稍有不同的是，数据范围大了点，原来用priority_queue的代码TLE。因为非常多次的插入操作。导致priority_queue的效率体现的不明显，所以直接替换掉。用最朴素的方法反而更快点。
AC代码：
#include <algorithm>
#include <queue>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std; const int maxn = 1002; int t[maxn], f[maxn], d[maxn]; struct node{
int f;
int d;
}; node fish[maxn], p[maxn]; int main(){
#ifdef sxk
freopen("in.txt", "r", stdin);
#endif // sxk int n, h;
while(scanf("%d%d", &n, &h)!=EOF){
h = h * 60;
for(int i=1; i<=n-1; i++) scanf("%d", &t[i]);
for(int i=1; i<=n; i++) scanf("%d", &fish[i].f);
for(int i=1; i<=n; i++) scanf("%d", &fish[i].d);
int maxans = 0;
for(int i=1; i<=n; i++){
int tc = 0;
for(int j=1; j<i; j++) tc += t[j];
for(int j=1; j<=i; j++) p[j] = fish[j]; //直接用数组取代priority_queue
int ans = 0;
int th = (h - tc) / 5;
for(int j=1; j<=th; j++){
int foo = 1;
for(int k=1; k<=i; k++) //遍历找最大值
if(p[k].f > p[foo].f) foo = k;
ans += p[foo].f;
p[foo].f -= p[foo].d;
if(p[foo].f < 0) p[foo].f = 0;
}
if(maxans < ans) maxans = ans;
}
printf("%d\n", maxans);
}
return 0;
}