题目是一个很典型的斜率优化的题目。题意就不说了。
是这样的，对于双端优先队列，我们共有队首和队尾两个删除操作，来保证对于任意一个i，第一个元素都是最优的。
我们把dp的转移方程列出来就直达其状态为f[i]=min(f[j]+(a[i]-a[j+1])^2+m)。
所以我们如果有j1<j2且j2优于j1，那么一定有2*a[i]*(a[j2+1]-a[j1+1])>=f[j2]-f[j1]+a[j2+1]-a[j1+1]。同时由于等式两边都是正数而且随着i的增大，a[i]也是变大的，所以只要等式一旦成立，那么对于后面的每一个a[i]，都是成立的，所以此时说明j1这个元素已经没有用了，因为它一定不会是后面的最优解。所以可以从对首删除，这样我们就完成了对首的操作。
接下来稍微难一点的是队尾的的操作。是这样的，假如当前我们需要加入i这个元素，我们再加入前对队尾倒数第二个，倒数第一个和i分别进行比较，分别记为j1,j2,i。
显然一定存在一个 x1使得j2由于j1，也一定存在一个x2使得i由于j2，这样我们只要比较一下x1和x2的大小就知道该怎么操作了。
什么意思呢？如果存在x1>=x2，也就说还没等到j2由于j1，i就已经优于j2了，那么显然j2也是无用的应该从队尾删除。
然后加入当前的元素i。这样我们又一次保证了队列中间的单调性。
恩，就是这样的，上代码吧 。。。 代码效率很低，求大神指教。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
#define maxn 1000100
using namespace std; ll a[maxn],f[maxn],q[maxn];
ll n,m,head,tail;
ll xx,yy,xx1,yy1; ll dy(ll j1,ll j2) { return f[j2]-f[j1]+a[j2+]*a[j2+]-a[j1+]*a[j1+]; } ll dx(ll j1,ll j2) { return *(a[j2+]-a[j1+]); } int main()
{
while (scanf("%I64d%I64d",&n,&m) && (n|m))
{
for (int i=; i<=n; i++) scanf("%I64d",&a[i]);
head=tail=,q[]=;
for (int i=; i<=n; i++)
{
while (head<tail)
{
xx=dx(q[head],q[head+]);
yy=dy(q[head],q[head+]);
if (xx*a[i]>=yy) head++;
else break;
}
f[i]=f[q[head]]+(a[i]-a[q[head]+])*(a[i]-a[q[head]+])+m;
while (head<tail)
{
xx=dx(q[tail-],q[tail]);
yy=dy(q[tail-],q[tail]);
xx1=dx(q[tail],i);
yy1=dy(q[tail],i);
if (yy*xx1>=yy1*xx) tail--;
else break;
}
q[++tail]=i;
}
printf("%I64d\n",f[n]);
}
return ;
}