能够非常好的证明单调决策性质。用   记sum[i]=sigma(C[1],C[2].....C[k]);f[i]=sum[i]+i;  c=l-1;

有转移dp[i]=min( dp[j]+(f[i]-f[jk]-c)^2);  假死 有2个决策j<k, 对于i点。k决策更优秀 于是能够得到

dp[k]+(f[i]-f[k]-c)^2<dp[j]+(f[i]-f[j]-c)^2;

对于一个x>i  如果f[x]=f[i]+v;对于决策j,k。若决策k优于决策j  ,必定

dp[k]+(f[x]-f[k]-c)^2<dp[j]+(f[x]-f[j]-c)^2;

于是dp[k]+(f[i]+v-f[k]-c)^2<dp[j]+(f[i]-v-f[j]-c)^2;

仅仅要2v(f[i]-f[k]-c)+v^2<2v(f[i]-f[j]-c)

优于v>0   f[k]>f[j]  这是必定成立的  ，所以能够非常好的证明单调决策性质。然后能够依据《1D/1D动态规划初步》论文的写法做。

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <cmath>

#include <string>

#include <cctype>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int inf  = 0x3fffffff;

const int mmax = 500010;

LL C[mmax];

LL dp[mmax];

LL sum[mmax];

int n;

LL L;

struct node

{

    int l,r;

    int d;

    node() {}

    node(int l,int r,int d):l(l),r(r),d(d) {}

    void print()

    {

        printf("%d %d %d\n",l,r,d);

    }

}Q[mmax];

LL sqr(LL x)

{

    return x*x;

}

void up(int i,int j)

{

    dp[i]=dp[j]+sqr(sum[i]-sum[j]+i-j-1-L);

}

bool ok(int i,int j,int d)

{

    return dp[d]+sqr(sum[i]-sum[d]+i-d-1-L)>=dp[j]+sqr(sum[i]-sum[j]+i-j-1-L);

}

int find(int l,int r,int j,int d)

{

    int mid;

    r++;

    while(l<r)

    {

        mid=(l+r)>>1;

        if(ok(mid,j,d))

            r=mid;

        else

            l=mid+1;

    }

    return r;

}

void make()

{

    int head=0,tail=0;

    dp[0]=0;

    Q[tail++]=node(0,n,0);

    for(int i=1;i<=n;i++)

    {

        while(Q[head].r<i)

            head++;

        if(Q[head].l<i)

            Q[head].l=i;

        up(i,Q[head].d);

        int tmp=0;

        while(head<tail)

        {

            if(ok(Q[tail-1].l,i,Q[tail-1].d))

            {

                tmp=Q[tail-1].l;

                tail--;

            }

            else

            {

                tmp=find(Q[tail-1].l,Q[tail-1].r,i,Q[tail-1].d);

                Q[tail-1].r=tmp-1;

                break;

            }

        }

        if(tmp<=n)

            Q[tail++]=node(tmp,n,i);

    }

}

int main()

{

    while(cin>>n>>L)

    {

        sum[0]=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%lld",&C[i]);

            sum[i]=sum[i-1]+C[i];

        }

        make();

        printf("%lld\n",dp[n]);

    }

    return 0;

}