Covered Walkway

//有状态转移方程dp[i]=min(dp[j]+C+(a[i]-a[j+1])*(a[i]-a[j+1])),数据是1e6的两重循环必然不行//设k<j<i,当到达i点时如果从j点转移到i比从k点转移到i更优则有:dp[j]+C+(a[i]-a[j+1])^2<dp[k]+C+(a[i]-a[k+1])^2//展开得:(dp[j]-dp[k]+a[j+1]^2-a[k+1]^2)/2*(a[j+1]-a[k+1])<a[i].其中a[i]常量(实现时是一重循环枚举i点)，//我们设yj=dp[j]+a[j+1]^2,xj=a[j+1] =>(yj-yk)/2*(xj-xk)<a[i].左边是计算斜率的式子。我们用一个单调队列//来存储能够转移到i点状态的点并且队头是转移到i点状态的最优的解，每次要保持队头是最优解就要根据//(yj-yk)/2*(xj-xk)<a[i]用队头去和队列中第二个去比较(如果队头不优于第二个就要删去队头元素)。//设g[i,j]表示直线j-i的斜率，如果有g[k,j]>g[i,j]那么j点永远不可能是i的最优解，因为：//我们假设g[i,j]<a[i]，那么就是说i点要比j点优，排除j点。如果g[i,j]>=a[i]，那么j点此时是比i点要更优，//但是同时g[j,k]>g[i,j]>sum[i]。这说明还有k点会比j点更优，同样排除j点。排除多余的点，这便是一种优化！//其实就是维护一个斜率递增的（下凸上凹）的图形。因此要把i点加入队列之前先判断是否能够维护斜率递增如果//不能就把队列最后一个元素删掉直到是斜率递增的然后加入i点。#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long long ll;const int maxn=1000009;int n,m,que[maxn];ll dp[maxn],a[maxn];ll getdp(int i,int j){    return dp[j]+m+(a[i]-a[j+1])*(a[i]-a[j+1]);}ll getup(int j,int k){    return dp[j]-dp[k]+a[j+1]*a[j+1]-a[k+1]*a[k+1];}ll getlow(int j,int k){    return 2*(a[j+1]-a[k+1]);}int main(){    while(scanf("%d%d",&n,&m)&&(n+m)){        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);        int head=0,tail=0;        dp[0]=0;        que[tail++]=0;        for(int i=1;i<=n;i++){            while(head+1<tail&&getup(que[head+1],que[head])<=a[i]*getlow(que[head+1],que[head]))                head++;            dp[i]=getdp(i,que[head]);            while(head+1<tail&&getup(que[tail-1],que[tail-2])*getlow(i,que[tail-1])>=getup(i,que[tail-1])*getlow(que[tail-1],que[tail-2]))                tail--;            que[tail++]=i;        }        printf("%lld\n",dp[n]);    }    return 0;}