题目
又是一道斜率dp题 而且还是套路题。
一般转移
for(LL i=1;i<=n;i++)A[i]=read(); for(LL i=1;i<=n;i++)sum[i]=(LL)sum[i-1]+i; f[1]=A[1]; for(LL i=2;i<=n;i++) { f[i]=~0u>>1; for(LL j=1;j<i;j++) f[i]=min(f[i],f[j]+(i-j)*i-(sum[i]-sum[j])+A[i]); }推出斜率((double)f[i]-f[j]+sum[i]-sum[j])/(double)((double)i-j)
依旧简单
#include<bits/stdc++.h> #define N 1000000 #define LL long long using namespace std; LL n; LL A[N+1],l,r,q[N+1]; LL sum[N+1],f[N+1]; inline char nc() { static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline LL read() { LL x=0; char c=nc(); while(c<'0'||c>'9')c=nc(); while(c<='9'&&c>='0')x=x*10+c-'0',c=nc(); return x; } double slope(LL i,LL j) { return (double)((double)f[i]-f[j]+sum[i]-sum[j])/(double)((double)i-j); } int main() { n=read(); for(LL i=1;i<=n;i++)A[i]=read(); for(LL i=1;i<=n;i++)sum[i]=(LL)sum[i-1]+i; // f[1]=A[1]; // cout<<f[1]<<" "; // for(LL i=2;i<=n;i++) // { // f[i]=~0u>>1; // for(LL j=1;j<i;j++) // { // f[i]=min(f[i],f[j]+(i-j)*i-(sum[i]-sum[j])+A[i]); // } // cout<<f[i]<<" "; // } // cout<<endl; memset(f,0,sizeof(f)); l=1,r=0,q[++r]=0; for(LL i=1;i<=n;i++) { while(l<r&&slope(q[l+1],q[l])<=i)l++; LL tmp=q[l]; f[i]=(LL)(A[i]+f[tmp]+i*i-i*tmp-sum[i]+sum[tmp]); while(l<r&&slope(i,q[r])<slope(q[r],q[r-1]))r--; q[++r]=i; } cout<<f[n]; return 0; }