题解 P1717 【钓鱼】
读完题很容易就会发现，这是一道求最优解的问题，于是乎，我们就可以想到两种方法：贪心和动态规划。
方法1（贪心+优先队列）
首先通过题目我们不难发现，为了得到最优解，那么就不能把时间浪费在路上，也就是说不能走回头路。然后很容易可以发现，在每个时刻在不同的鱼塘钓到的鱼的数量是不同的，为了保证钓到最多的鱼，那么我们每次钓都要选当前可以钓到鱼数量最多的鱼塘，钓完之后就更新这个鱼塘的钓鱼数量，再进行下一轮的钓鱼。
那么现在就出现一个问题：如果要想按照上面的贪心方法，每次到可以钓到鱼的数量最多的鱼塘里去钓鱼，那么就很可能出现要在几个鱼塘之间来来去去，会把时间浪费在路上。
怎样解决这个问题呢？
我们可以先确定可以走到的最远的鱼塘i，然后把时间减去从鱼塘1走到鱼塘i的时间，在剩下的时间里一直钓鱼，可以假设钓鱼人可以瞬间移动，在鱼塘1到鱼塘i之间采用上面的贪心方法，就可以求到最远走到鱼塘i的最优解。
为什么可以假设钓鱼人可以瞬间移动呢？
因为钓鱼人的钓鱼的范围是从鱼塘1到鱼塘i，所以他花的最少的移动时间就是从鱼塘1到鱼塘i的时间，那么剩下来的时间就可以全部用来钓鱼，那么这时我们要考虑的并不是钓鱼的次序，而是钓了哪几次鱼，也就是说，我们只要知道每次钓的鱼是在哪里钓的就行了，并不要知道从鱼塘1出发之后的钓鱼过程，而上面提到的贪心算法，恰恰求的就是每次钓的鱼是在哪里钓的。
解决了这个问题，那么还有一个问题：在实现贪心算法的时候，如何每次快速找到目前钓鱼数量最多的鱼塘并且实时更新鱼塘的钓鱼数量呢？
常规的话，就是要全部扫一遍，找到最大值，然后更新就更为麻烦，不可取。这时，就想到一种很高效的求最值的数据结构——优先队列。我们可以用一个优先队列，来储存当前可以钓到的鱼塘钓鱼数量，只要维护一个大根堆，就可以很容易地实现得到最大值和更新。
我们最后来总结一下贪心+优先队列的方法，我们以5分钟为一个单位时间，穷举所有可以到达的最远鱼塘，每次都用总时间减去花在路上的时间，也就是从鱼塘1到目前最远鱼塘的距离，就得到钓鱼的时间，然后就用贪心来求到当前情况下的最优解，贪心时取最大值和更新用优先队列来实现，最后在所有的最优解中选取一个最大的就得到最终答案。
方法2（动态规划）
很容易就可以发现，这道题目适合用动态规划来解决。
我们以5分钟为一个单位时间，定义一个数组opt，opt[i][j]则表示走到第i个池塘花j个单位时间可以钓到的最大鱼数。
我们设在池塘i花了k个单位时间钓鱼，从池塘i-1走到池塘i要花t[i-1]的时间。那么opt[i][j]就等于opt[i][j-t[i-1]-k]（即到上一个池塘花j-池塘i-1到池塘i的时间-k的单位时间的最优解）加上在池塘i花k个单位时间钓到的鱼，那么就可以得到
opt[i][j]=max{opt[i-1][j-t[i-1]-k]+k*f[i]-d[i]-2*d[i]-3*d[i]-…-(k-1)*d[i]}
化简一下得到
opt[i][j]=max{opt[i-1][j-t[i-1]-k]+k*f[i]-k*(k-1)/2*d[i]}
确定了状态转移方程，现在就要来看k的取值范围。很容易就可以知道，数组下标不能为负，所以k必须<=j-t[i-1]；由于钓的鱼的数量为正，所以(k-1)*d[i]<f[i]；还有一点最重要，就是因为到除池塘1之外的池塘都需要时间，所以opt[i][0]（i>1）是无意义的的，所以当k要保证opt[i][j-t[i-1]-k]有意义，那我们一开始初始化的时候把opt都赋值成-1，表示无意义，只把opt[0][0]赋值为0，因为这样可以保证opt[1][*]有意义，从而保证其他的有意义。
这样，很简单就可以求到最优解了。
源代码
方法1（贪心+优先队列）
#include<bits/stdc++.h>
using namespace std;
int const maxn=10001;
struct node{
int f,num;
bool operator <(node x)const{
return f<x.f;
}
}a[maxn];
int n,h,i,j,k,d[maxn],t[maxn],ans;
priority_queue<node>q;
int main(){
cin>>n>>h;
h*=12;
for(i=1;i<=n;++i){
cin>>a[i].f;
a[i].num=i;
}
for(i=1;i<=n;++i)
cin>>d[i];
for(i=1;i<n;++i)
cin>>t[i];
for(i=1;i<=n;++i){ //穷举最远走到的鱼塘
h-=t[i-1]; //更新总钓鱼时间
int now=0;
while(!q.empty()) //清空原堆
q.pop();
for(j=1;j<=i;++j) //构造现在的大根堆
q.push(a[j]);
for(j=1;j<=h;++j){
node s;
s=q.top(); //取最大值
if(s.f>0)
now+=s.f; //更新已经钓到鱼的数量
s.f-=d[s.num]; //减少可以钓到鱼的数量
q.pop(); //用过的出堆
q.push(s); //插入更新后的
}
ans=max(ans,now); //更新答案
}
cout<<ans<<endl;
return 0;
} 方法2（动态规划）
#include<bits/stdc++.h>
using namespace std;
int opt[30][10000],i,j,k,f[30],d[30],t[30],n,h,ans=-1;
int main(){
cin>>n>>h;
h*=12;
for(i=1;i<=n;++i)
cin>>f[i];
for(i=1;i<=n;++i)
cin>>d[i];
for(i=1;i<n;++i)
cin>>t[i];
memset(opt,-1,sizeof(opt));
opt[0][0]=0;
for(i=1;i<=n;++i)
for(j=1;j<=h;++j){
for(k=0;k<=j-t[i-1];++k)
if((k-1)*d[i]<f[i]&&opt[i-1][j-t[i-1]-k]!=-1){
opt[i][j]=max(opt[i][j],opt[i-1][j-t[i-1]-k]+k*f[i]-k*(k-1)/2*d[i]);
ans=max(ans,opt[i][j]);
}
}
cout<<ans<<endl;
return 0;
}