本文主要是介绍zoj3627 Treasure Hunt II 贪心+模拟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：n个城市在一条直线，相邻城市距离为1，每个城市都有一些宝藏。他们从p城市出发，有两个限制：1.他们只能在T时间内寻宝
2.他们两人的距离不能超过M，问他俩最多能获得的宝藏值。
思路：首先一开始他俩一定按相反方向跑，直至相距M（如果T小到无法形成M，直接输出T时间两人能走到的最左端到能走到的最右段
的宝藏和），如果M为奇数，那么你要分是左边的人向左，还是右边的人向右。接下来分两种情况，(1)先向左后向右 (2)先向右后向左
分别枚举一开始向左、向右走的天数，最后对所有情况球个最大值即可。相见代码：
// file name: A.cpp //
// author: kereo //
// create time: 2014年08月26日 星期二 12时16分24秒 //
//***********************************//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=100000+100;
const int inf=0x3fffffff;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
int n,p,m,T;
int a[MAXN];
ll sum[MAXN];
int main()
{while(~scanf("%d%d",&n,&p)){sum[0]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}scanf("%d%d",&m,&T);int x=m/2;x=min(x,T);int l,r;l=max(1,p-x);r=min(n,p+x);int d=max(r-p,p-l);ll ans;if(T<=x){ans=sum[r]-sum[l-1];cout<<ans<<endl;continue;}int flag1=0,flag2=0;if(l>1)flag1=1;if(r<n)flag2=1;//向左扩1ans=sum[r]-sum[l-1];if(flag1){int L=l-1,R=r;if(m%2 == 0)L=l;ans=max(ans,sum[R]-sum[L-1]);int t=T-d-1; //剩余时间if(m%2 ==0)t+=1;for(int i=1;i<=min(L-1,t);i++){ll res=sum[L-1]-sum[L-i-1];int t1=t-i;int Rr=min(L-i+m+t1,n);res+=max((ll)0,sum[Rr]-sum[R]);ans=max(ans,res+sum[R]-sum[L-1]);}for(int i=1;i<=min(t,n-R);i++){ll res=sum[R+i]-sum[R];int t1=t-i;int Ll=max(1,R+i-m-t1);res+=max((ll)0,sum[L-1]-sum[Ll-1]);ans=max(ans,res+sum[R]-sum[L-1]);}}//向右扩1if(flag2){int L=l,R=r+1;int t=T-d-1;if(m%2 == 0)R=r,t+=1;ans=max(ans,sum[R]-sum[L-1]);for(int i=1;i<=min(L-1,t);i++){ll res=sum[L-1]-sum[L-i-1];int t1=t-i;int Rr=min(L-i+m+t1,n);res+=max((ll)0,sum[Rr]-sum[R]);ans=max(ans,res+sum[R]-sum[L-1]);}for(int i=1;i<=min(t,n-R);i++){ll res=sum[R+i]-sum[R];int t1=t-i;int Ll=max(1,R+i-m-t1);res+=max((ll)0,sum[L-1]-sum[Ll-1]);ans=max(ans,res+sum[R]-sum[L-1]);}}cout<<ans<<endl;}return 0;
}这篇关于zoj3627 Treasure Hunt II 贪心+模拟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
