题解：P15289 「YLLOI-R3-T4」止战之殇

Moss345512 · 2026-02-12 18:49:36 · 题解

原题：P15289

算法分析

考虑四种贪心策略：

• 一直往左走
• 一直往右走
• 往左走到头后一直往右走
• 往右走到头后一直往左走

只需输出每种策略答案的最大值即可。

这是我的赛时思路，前两种策略可能不需要

设当前在第 t 对怪兽之间

一直往左走：

由于不用回头，所以可以先在原地待。

• 第一步：在原地待，直到不能再待了（\text{Ans}\gets \text{Ans}+\frac{(c_t-2)}{2d},c_t\gets (c_t-2)\bmod 2d）
• 第二步：判断
  • 如果还能往左跳一格（c_{t-1}\ge2d+2），就往左跳一格（t\gets t-1），回到第一步
  • 否则如果还能往左跳两格（c_{t-2}\ge2d+2），就往左跳两格（t\gets t-2），回到第一步
  • 否则就再也走不了了，退出

一直往右走同理

往左走到头后一直往右走：

往左走：

• 第一步：判断
  • 如果还能往左跳一格甚至还能在那再待一回合（c_{t-1}\ge4d+2），就往左跳一格（t\gets t-1）
  • 否则如果还能往左跳两格甚至还能在那再待一回合（c_{t-2}\ge4d+2），就往左跳两格（t\gets t-2）
  • 否则如果左边两格都能跳但都不能再待一回合（2d+2\le c_{t-1}\le4d+2,2d+2\le c_{t-2}\le4d+2），就往左跳两格（这是为了保证等会能跳回来）
  • 否则判断
  • 如果还能往左跳两格（c_{t-2}\ge2d+2），就往左跳两格，退出往左走的过程
  • 否则如果还能往左跳一格（c_{t-1}\ge2d+2），就往左跳一格，退出往左走的过程
  • 否则，直接退出往左走的过程
• 第二步：在原地待一回合，回到第一步

然后就一直往右走，同上。\ 往右走到头后一直往左走同理。

程序实现

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a,t;
long long d,b[1000005],c[1000005],ans,tmp;
int main(){
    scanf("%d %d %lld",&n,&a,&d);
    for(int i=1;i<n;i++)scanf("%lld",&b[i]);

    //LEFT：一直向左
    tmp=0;
    for(int i=1;i<n;i++)c[i]=b[i];
    for(t=a;;){
        // printf("%d ",t);
        tmp+=(c[t]-2)/(2*d);
        c[t]-=(c[t]-2)%(2*d);
        if(t>1 && c[t-1]-2>=2*d)t--; // 跳
        else if(t>2 && c[t-2]-2>=2*d)t-=2; // 跳
        else break;
    }
    // printf("\n");
    ans=max(ans,tmp); // 更新答案

    //RIGHT：一直向右
    tmp=0;
    for(int i=1;i<n;i++)c[i]=b[i];
    for(t=a;;){
        // printf("%d ",t);
        tmp+=(c[t]-2)/(2*d);
        c[t]-=(c[t]-2)%(2*d);
        if(t<n-1 && c[t+1]-2>=2*d)t++; // 跳
        else if(t<n-2 && c[t+2]-2>=2*d)t+=2; // 跳
        else break;
    }
    // printf("\n");
    ans=max(ans,tmp); // 更新答案

    //LEFT->RIGHT：先左后右
    tmp=0;
    for(int i=1;i<n;i++)c[i]=b[i];
    for(t=a;;){
        // printf("%d ",t);
        if(c[t]-2>=4*d)tmp++,c[t]-=2*d;
        if(t>1 && c[t-1]-2>=4*d)t--; // 跳
        else if(t>2 && c[t-2]-2>=4*d)t-=2; // 跳
        else if(t>2 && c[t-2]-2>=2*d && c[t-1]-2>=2*d)t-=2; // 跳
        else break;
    }
    if(t>2 && c[t-2]-2>=2*d)t-=2;
    else if(t>1 && c[t-1]-2>=2*d)t--;
    for(;;){ // 往回跳
        // printf("%d ",t);
        tmp+=(c[t]-2)/(2*d);
        c[t]-=(c[t]-2)%(2*d);
        if(t<n-1 && c[t+1]-2>=2*d)t++; // 跳
        else if(t<n-2 && c[t+2]-2>=2*d)t+=2; // 跳
        else break;
    }
    // printf("\n");
    ans=max(ans,tmp); // 更新答案

    //RIGHT->LEFT：先右后左
    tmp=0;
    for(int i=1;i<n;i++)c[i]=b[i];
    for(t=a;;){
        // printf("%d ",t);
        if(c[t]-2>=4*d)tmp++,c[t]-=2*d;
        if(t<n-1 && c[t+1]-2>=4*d)t++; // 跳
        else if(t<n-2 && c[t+2]-2>=4*d)t+=2; // 跳
        else if(t<n-2 && c[t+2]-2>=2*d && c[t+1]-2>=2*d)t+=2; // 跳
        else break;
    }
    if(t<n-2 && c[t+2]-2>=2*d)t+=2;
    else if(t<n-1 && c[t+1]-2>=2*d)t++;
    for(;;){ // 往回跳
        // printf("%d ",t);
        tmp+=(c[t]-2)/(2*d);
        c[t]-=(c[t]-2)%(2*d);
        if(t<n-1 && c[t+1]-2>=2*d)t++; // 跳
        else if(t<n-2 && c[t+2]-2>=2*d)t+=2; // 跳
        else break;
    }
    // printf("\n");
    ans=max(ans,tmp);

    printf("%lld",ans);
    return 0;
}