题解：CF1091F New Year and the Mallard Expedition

ingo_dtw · 2026-10-20 15:10:47 · 题解

首先如果全程都飞是肯定最优的，假设 D=\sum_{i=1}^n d_i 那么答案就是 D。

但是，这样消耗的体力也是 D 考虑我们有什么方式可以获得体力。

对于一米游泳，如果我们把一米飞行换成游泳，那么时间增加 2 获得 2 体力，可以看做时间增加 1 体力增加 1，一段长度为 d 米的水面可以提供 2d 个这样的机会。

而对于一米将飞行换成走路，步行，那么时间增加 4 体力增加 2，我们同样看作时间增加 2 体力增加 1 一段长度为 d 的草地也可以获得 2d 个这样的机会。

还有就是，我们可以通过往回走半米再走回来。

对于在水面，位移为 0 时间花费 3 体力增加 1 可以走无限次。

对于陆地，位移为 0 时间花费 5 体力增加 1 同样无限次。

对于上面的情况，优先级显然是递减的。

:::success[Ac Code]

#include <bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long
#define _ read<int>()
#define rint register int
inline bool blank(const char &x)
{
    return !(x^13)||!(x^9)||!(x^32)||!(x^10);
}
template<class T>inline T read()
{
    T r=0,f=1;char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();(x^-1)&&blank(x);x=gc());
}
const int N=1e5+5;
int d[N];
char s[N];
signed main()
{   
    rint n=_,ans=0,D=0;
    for(rint i=1;i<=n;++i) d[i]=_,ans+=d[i];
    D=ans;
    for(rint i=1;i<=n;++i) read(s[i]);
    rint g=0,w=0;
    bool fg=0,fw=0;
    for(rint i=1;i<=n;++i)
    {
        if(s[i]=='G') g+=(d[i]<<1),fg=1; 
        else if(s[i]=='W') w+=(d[i]<<1),fw=1;
        rint k=d[i];
        rint x=min(k,w);
        k-=x,w-=x,ans+=x;
        x=min(k,g);
        k-=x,g-=x,ans+=(x<<1);
        if(k)
        {
            ans+=(fw?3:5)*k;
        }
    }
    out(ans);
    return 0;
}//穗穗平安~

:::