CF1768F Wonderful Jump 题解

考虑 dp，记 \(f_i\) 表示跳到位置 \(i\) 的最小代价，考虑哪些状态会对当前状态有贡献。

考虑状态 \(f_j\) 对当前状态有贡献需要满足什么条件，发现如果存在 \(j<k<i\) 满足 \(a_k=\min(a_j,a_{j+1},\dots,a_i)\)，则先跳到 \(k\) 再跳到 \(i\) 会更优。可得 \(\min(a_j,a_{j+1},\dots,a_i)\in\{a_j,a_i\}\)。

考虑对 \(i-j\) 进行根号分治，当 \(i-j\le \sqrt n\) 时，直接暴力更新即可。当 \(i-j>\sqrt n\) 时，因为代价不会超过 \(n(i-j)\)（每次跳一个），所以 \(\min(a_j,a_{j+1},\dots,a_i)<\sqrt n\)。

分 \(\min(a_j,a_{j+1},\dots,a_i)=a_j/a_i\) 两种情况考虑即可。对于等于 \(a_i\) 的情况，发现 \(a_i<\sqrt n\)，直接暴力枚举。对于等于 \(a_j\) 的情况，初始 \(j\) 为左边第一个满足 \(a_j\le a_i\) 的位置，每次跳到左边第一个小于当前 \(a_j\) 的位置更新即可。

时间复杂度 \(\mathcal O(n\sqrt n)\)。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 400003
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
int n,t,ls,q[mxn],a[mxn],l1[mxn],l2[mxn],l3[mxn];
ll dp[mxn];
signed main(){scanf("%d",&n);const int b=sqrt(n);rep(i,1,n)scanf("%d",&a[i]);rep(i,1,n){while(t&&a[q[t]]>a[i])t--;l1[i]=q[t];q[++t]=i;}t=0;rep(i,1,n){while(t&&a[q[t]]>=a[i])t--;l2[i]=q[t];q[++t]=i;}rep(i,1,n){if(a[i]<=b)ls=i;l3[i]=ls;}rep(i,2,n){dp[i]=n*(i-1ll);int mn=a[i];drep(j,i-1,max(1,i-b)){mn=min(mn,a[j]);dp[i]=min(dp[i],dp[j]+(ll)(i-j)*(i-j)*mn);}int k=l3[l1[i]];if(a[i]<=b){drep(j,i-1,1){if(a[j]<=a[i])break;dp[i]=min(dp[i],dp[j]+(ll)(i-j)*(i-j)*a[i]);}}while(k){dp[i]=min(dp[i],dp[k]+(ll)(i-k)*(i-k)*a[k]);k=l2[k];}}rep(i,1,n)cout<<dp[i]<<' ';return 0;
}