【洛谷P1717】钓鱼

题目大意：给定 N 个位置，每个位置有一个答案贡献值，在一个位置加了一次该位置的答案贡献值之后，该值会减掉一部分，从一个位置移动到另一个位置需要花费一定的时间，问：给定 M 单位的时间，如何移动使得答案贡献值最大。（初始在1位置）

题解：
引理：若想使答案贡献值最大，一定不能走回头路，因为走回头路时，可以在之前那个位置时就加一次答案贡献值，这样不会使结果更糟，证毕。
再考虑一个更简单的问题，即：没有移动的时间花费，那么就可以直接贪心，每次选序列中最大的数即可。因此，根据引理，可以枚举最远能够到达的位置，在开始时直接减掉从起点到该位置所有的跑路时间，把问题转化为没有移动的时间花费，直接贪心出答案，并更新最优解即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;

const int maxn=30;

int n,h,ans,f[maxn],d[maxn],t[maxn];

void read_and_parse(){

	scanf("%d%d",&n,&h),h*=12;

	for(int i=1;i<=n;i++)scanf("%d",&f[i]);

	for(int i=1;i<=n;i++)scanf("%d",&d[i]);

	for(int i=1;i<n;i++)scanf("%d",&t[i]);

}

void solve(){

	priority_queue<P> q;

	for(int i=1;i<=n;i++){

		int tot=0,s=h;

		while(q.size())q.pop();

		for(int j=1;j<i;j++)s-=t[j];

		for(int j=1;j<=i;j++)q.push(make_pair(f[j],j));

		for(int j=1;j<=s;j++){

			P now=q.top();q.pop();

			if(now.first<=0)break;

			tot+=now.first,now.first-=d[now.second];

			q.push(now);

		}

		ans=max(ans,tot);

	}

	printf("%d\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}