自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:06:31，当前版本为作者最后更新于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;
}