Wonderful Jump
题目看错了,以为能往回跳......
暴力转移式
\[dp_i=min(dp_i,dp_j+\min_{k=j}^ia_k\times(i-j)^2)
\]
你会发现这个没啥单调性,不好用数据结构维护。
所以考虑发掘性质,设 \(x=\min_{k=j}^ia_k\),那么一个宽松的上界是 \((i-j)\leq\lfloor\frac{n}{x}\rfloor\)
对于 \(x\geq\sqrt n\),可以得到\((i-j)\leq\sqrt n\),直接 \(\Omicron(n\sqrt n)\) 枚举,这是第一种转移。
讨论 \((i-j)>\sqrt n\)
不难发现 \((i-j)^2\geq(k-j)^2+(i-k)^2\),这说明当从 j 跳到 i 最优时 \(x=a_j\) 或 \(x=a_i\)。
1.\(x=a_j\)
这时 \(a_j\leq\sqrt n\),否则一定不会比第一种转移优,所以记录 \(a_k\leq\sqrt n\) 的最后一个位置 k。
为什么我们不用之前与 \(a_k\) 值相同的位置 \(k1\),讨论一下 k1 和 k 之间的值就会发现这样最优。复杂度 \(\Omicron(n\sqrt n)\)。
2.\(x=a_i\)
不难发现此时 \(a_i\leq\sqrt n\) 那么往前枚举 j 直到 \(a_j\leq a_i\),复杂度 \(\Omicron(n\sqrt n)\)。
以上三种不重不漏。
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
#define ll long long
const int MAXN=4e5+5;
const ll INF=1e18;
int n,B,a[MAXN],wz[MAXN],BB;
ll dp[MAXN];
int main(){
scanf("%d",&n);B=sqrt(n);BB=B+4;for(int i=1;i<=n;i++) scanf("%d",&a[i]),dp[i]=INF;dp[1]=0;
wz[a[1]]=1;
for(int i=2;i<=n;i++){
int mi=a[i];
for(int j=i-1;j>=max(1,i-BB+1);j--){
mi=min(mi,a[j]);dp[i]=min(dp[i],dp[j]+1ll*mi*(i-j)*(i-j));
}
for(int j=1;j<=B;j++){
if(!wz[j]) continue;
dp[i]=min(dp[i],dp[wz[j]]+1ll*j*(i-wz[j])*(i-wz[j]));
}
wz[a[i]]=i;
if(a[i]<=B){
for(int j=i-1;j>=1;j--){
if(a[j]<=a[i]) break;
dp[i]=min(dp[i],dp[j]+1ll*a[i]*(i-j)*(i-j));
}
}
}
for(int i=1;i<=n;i++) printf("%lld ",dp[i]);return 0;
}