真的,这数据是个很厉害 (贱) 的人出的
DP题,n2不过斜率过。那就加个斜率优化吧。
DP式:
f[i]=min{f[j]+(i-j)*(i-j-1)/2+a[i]};
我们依旧设k<j<i,且j比k更优
f[j]+(i-j) * (i-j-1)/2+a[i]<f[k]+(i-k) * (i-k-1)/2+a[i]
化简后,变为:
f[j]+j * (j+1)/2-f[k]-k * (k+1)/2<i
特别提醒一下:i * (i+1) 会爆 long long!!!(wdf)
上标:
#include<cstdio>
#define N 1000010
#define db double
#define ll long long
using namespace std;
int n,g[N],len=0,l=0;
ll f[N],a[N],b[N];
inline int read()
{
int x=0; char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
db solve(int x,int y) {return (db)(f[x]+b[x]-f[y]-b[y])/(x-y);}
int main()
{
// freopen("3156.in","r",stdin);
// freopen("3156.out","w",stdout);
n=read();
for (int i=1;i<=n;i++)
a[i]=read(),b[i]=(ll)i*(i+1)>>1;
for (int i=1;i<=n;i++)
{
while (l<len && solve(g[l+1],g[l])<i) l++;
f[i]=f[g[l]]+(ll)(i-g[l])*(i-g[l]-1)/2+a[i];
while (len>l && solve(g[len],g[len-1])>solve(i,g[len])) len--;
g[++len]=i;
}
printf("%lld
",f[n]);
return 0;
}