裸题，注意：基本的判断（求Min还是Max），因为是顺着做的，且最后一个a[i]一定要取到，所以是f[n]。
DP:f[i]=min(f[j]+(i-j-1)*(i-j)/2+a[i])
依旧设x>y且f[x]优于f[y]（原来是通用方法。。。）
2*(f[x]-f[y]) +x^2+x-y^2-y=2*i*(x-y) ok了。
#include <iostream>
#include <cstdio>
#define N 1000000+100
#define ll long long
using namespace std;
ll f[N];
int a[N],q[N];
int n,i,l,r;
inline int read()
{
int ans=,f=;
char c;
while (!isdigit(c=getchar())) if (c=='-') f=-;
ans=c-'';
while (isdigit(c=getchar())) ans=ans*+c-'';
return ans*f;
}
inline ll Pow(ll x) {return x*x;}
inline double Get(int x,int y) {return (double)(*(f[x]-f[y])+Pow(x)-Pow(y)+x-y)/(double)(x-y);}
int main()
{
n=read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<=n;i++)
{
while (l<r && Get(q[l+],q[l])<*i) l++;
f[i]=f[q[l]]+(i-q[l]-)*(i-q[l])/+a[i];
while (l<r && Get(i,q[r])<Get(q[r],q[r-])) r--;
q[++r]=i;
}
printf("%lld",f[n]);
return ;
}
Description
Input
第一行为一个整数N表示战线的总长度。
第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。
Output
共一个整数，表示最小的战线花费值。
Sample Input
10
2 3 1 5 4 5 6 3 1 2
Sample Output
18
HINT
1<=N<=10^6,1<=Ai<=10^9