AT2171 [AGC007D] Shik and Game 题解

Description

Luogu传送门

Solution

考虑一下 Shik 走路的全过程——不停地来回走。

有的路段只经过了一次,有的经过了三次。

那么我们设 \(f_i\) 表示拿到了前 \(i\) 个金币所花费的最小时间,由于是最小时间,那么他必定在 \(a_i\) 这个位置上。

转移方程:

\[f_i = min\{f_j + (a_i - a_j) + max(2(a_i - a_{j + 1}), T)\} \]

这是什么意思呢?

  • 第一个 \(a_i - a_j\) 表示的是从 \(a_j\) 走到 \(a_i\) 花费的时间。

  • \(2(a_i - a_{j + 1})\) 指折返回去再走回来,所以要乘 2。

  • \(T\) 是因为可能折回去之后还没有金币,所以还得等到 \(T\),所以要取 \(\max\)

不难发现,\(a_i - a_j\) 的和就是 \(a_n\),所以可以不用管,最后输出答案的时候加上 \(E\) 即可。

再来看如何转移,要分类讨论一下:

  • \(2(a_i - a_{j + 1}) > T\) 时,\(f_i = f_j + T\).
  • \(2(a_i - a_{j + 1}) \leq T\) 时,\(f_i = f_j + 2(a_i - a_{j + 1})\).

容易发现,对于固定的 \(i\)\(a_i - a_{j + 1}\)\(j = 1 \sim i - 1\) 时是单调递减的,所以直接单调队列跑一遍即可,或者拿个指针扫一遍也行。

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

namespace IO{
    inline ll read(){
        ll x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const ll N = 1e5 + 10;
ll n, E, T, l, mins = 1e18;
ll a[N], f[N];
ll q[N], head, tail;

signed main(){
    n = read(), E = read(), T = read();
    for(ll i = 1; i <= n; ++i) a[i] = read();
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    head = 1, tail = 1;
    for(int i = 1; i <= n; ++i){
        while(head <= tail && 2 * (a[i] - a[q[head] + 1]) > T)
            mins = min(mins, f[q[head]] - 2 * a[q[head] + 1]), head++;
        f[i] = min(f[i], min(f[q[head]] + T, mins + 2 * a[i]));
        q[++tail] = i;
    }
    write(f[n] + E);
    return 0;
}

\[\_EOF\_ \]

原文地址:https://www.cnblogs.com/xixike/p/15712797.html