题解：P11333 [NOISG2020 Finals] Discharging

Purslane · 2024-12-30 18:58:30 · 题解

Solution

考虑如果某一段 [l,r] 的最大值为 a_k，则必定有 a_{r+1} > k，否则 r \leftarrow r+1 肯定更优。

因此我们只考虑前缀最大值之间的转移，可以令 a_i \leftarrow \max_{1 \le j \le i} a_j，答案不变。

这样就有

显然可以斜率优化。

#include<bits/stdc++.h>
#define int long long
#define _ ((__int128)1)
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e6+10;
int n,a[MAXN],dp[MAXN],tot,pos=1;
struct Node {int x,y;}st[MAXN];
void insert(int x,int y) {
    while(tot>1&&_*(y-st[tot].y)*(st[tot].x-st[tot-1].x)<_*(st[tot].y-st[tot-1].y)*(x-st[tot].x)) tot--;
    return st[++tot]={x,y},void();  
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n) cin>>a[i];
    ffor(i,1,n) a[i]=max(a[i],a[i-1]);
    insert(0,0);
    ffor(i,1,n) {
        while(pos<tot&&_*a[i]*(st[pos+1].x-st[pos].x)>st[pos+1].y-st[pos].y) pos++;
        while(pos>1&&_*a[i]*(st[pos].x-st[pos-1].x)<st[pos].y-st[pos-1].y) pos--;
        dp[i]=n*a[i]+st[pos].y-st[pos].x*a[i];
        insert(i,dp[i]),pos=min(pos,tot);
    }
    cout<<dp[n];
    return 0;
}