【ZOJ3627】Treasure Hunt II

题目大意：给定一个长度为 N 的序列，现有两个人从 P 点出发，每个单位时间每个人最多可以移动一个单位，两人之间的最大距离不能超过 M，一共有 T 单位的时间，求在合法情况下，两人可以获得的序列点权和最大是多少。

题解：模拟+贪心

首先考虑最开始的情况，在合法的情况下肯定是扩展的越大越好，在这里用了一个贪心。需要注意的是，若 M 为奇数，则要讨论最后一步谁来走。再根据剩余的时间进行枚举多少步向左走，多少步向右走，统计答案即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

typedef long long LL;

int n,m,t,p;

LL sum[maxn],ans;

void read_and_parse(){

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

		scanf("%lld",&sum[i]);

		sum[i]+=sum[i-1];

	}

	scanf("%d%d",&m,&t);

	ans=0;

}

void getans(int l,int r,int rest){

	LL ret=0;

	for(int k=0;k<=rest;k++){ // left

		if(l-k<1)break;

		int lb=l-k,rb=min(n,max(r+rest-2*k,r));

		ret=max(ret,sum[rb]-sum[lb-1]);

	}

	for(int k=0;k<=rest;k++){ // right

		if(r+k>n)break;

		int rb=r+k,lb=max(1,min(l,l+2*k-rest));

		ret=max(ret,sum[rb]-sum[lb-1]);

	}

	ans=max(ans,ret);

}

void solve(){

	int lb=max(1,p-t),rb=min(n,p+t);

	if(rb-lb<=m){

		printf("%lld\n",sum[rb]-sum[lb-1]);

		return;

	}

	if(m&1){

		int l=max(1,p-m/2),r=min(n,p+m/2);

		int rest=t-m/2-1;

		getans(l,r+1,rest),getans(l-1,r,rest);

	}else{

		int l=max(1,p-m/2),r=min(n,p+m/2);

		int rest=t-m/2;

		getans(l,r,rest);

	}

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

}

int main(){

	while(scanf("%d%d",&n,&p)!=EOF){

		read_and_parse();

		solve();

	}

	return 0;

}

巴特西

【ZOJ3627】Treasure Hunt II

最新文章

热门文章