Secret Letters

_ANIG_ · 2023-11-17 19:23:26 · 题解

Secret Letters

枚举第一封信是什么时候寄存的。

若另一方来取信，则会再次寄存一个。

所以可以看作一个信从一开始寄存到了结尾。

这样，第一次取信就可以看作是免费的。

贪心地，每次能取信就取信。

这样每个信在什么时候取就固定了，每个信寄存的代价也固定了，直接和 d 取个 \min 就是对答案的贡献。

后缀和预处理一下就可以 O(n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int p[N],op[N],n,w1,w2,res,eds,nxt[N],hz[N];
signed main(){
    cin>>n>>w1>>w2;
    for(int i=1;i<=n;i++){
        char c;
        scanf("%lld %c",&p[i],&c);
        op[i]=c=='P';
    }
    cin>>p[n+1];op[n+1]=2;
    for(int i=n;i>=1;i--){
        if(op[i+1]!=op[i])nxt[i]=i+1;
        else nxt[i]=nxt[i+1];
        hz[i]=hz[i+1];
        if(op[i]==op[i-1])hz[i]+=min(w2,w1*(p[nxt[i]]-p[i]));
    }
    res=n*w2;
    for(int i=1;i<=n;i++)res=min(res,w1*(p[n+1]-p[i])+hz[i+1]+(i-1)*w2);
    cout<<res;
}