【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

原文：https://www.cnblogs.com/wzj-xhjbk/p/10928971.html