Evanyou Blog 彩带

　　题目传送门

---

　　分析：数据范围并不大，也不难想到是贪心。因为钓鱼和移动的时间都是5的倍数，而且给定的h以小时为单位，所以在输入的时候可以直接将h乘以12，然后每次钓鱼花费的时间就是1，移动花费的时间就是t[i]。但是因为题目中给定了多个湖泊，而且每次钓鱼后鱼的数量会减少，因此还要考虑最优化策略。当然这里蒟蒻想了很久，还是没有确定的思路，还是靠着ACX大佬的指导才想明白一种非常奇（xuan）妙（xue）的思路：首先从1-n枚举，表示本次会在前i个湖泊内钓鱼。然后直接从h中减去移动花费的时间，接下来就只需要考虑钓鱼就行了。可以用优先队列实现。其实思路真的不难（只是难想到）。具体看代码吧。

　　Code：

　　

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<queue>
using namespace std;
const int N=10001;
int n,h,d[N],t[N],ans;
struct Fish{
  int f,id;
  bool operator < (Fish a) const{
    return f<a.f;}
}f[N];
priority_queue<Fish>team;
inline void ready()
{
  cin>>n>>h;h*=12;
  for(int i=1;i<=n;i++)
    cin>>f[i].f,f[i].id=i;
  for(int i=1;i<=n;i++)
    cin>>d[i];
  t[1]=0;
  for(int i=2;i<=n;i++)
    cin>>t[i];
}
inline void work()
{
  for(int i=1;i<=n;i++){
    h-=t[i];
    int now=0;
    while(!team.empty())
      team.pop();
    for(int j=1;j<=i;j++)
      team.push(f[j]);
    for(int j=1;j<=h;j++){
      Fish x;
      x=team.top();
      team.pop();
      if(x.f>0)
      now+=x.f;
      x.f-=d[x.id];
      team.push(x);
    }
    ans=max(ans,now);
  }
  cout<<ans<<endl;
}
int main()
{
  ios::sync_with_stdio(false);
  ready();
  work();
  return 0;
}