POJ3709[K-Anonymous Sequence]

动态规划,斜率优化,具体见这里


CODE:


 /*


AUTHOR: Su Jiao


DATE: 2010-8-22


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using namespace std;


 


const long long int oo=0X19930309*19930309;


const int MAXN=500000+2;


int T;


int n,k;


long long int a[MAXN];


long long int s[MAXN];


long long int f[MAXN];


int q[MAXN];


int head,tail;


 


int main()


{


    ios::sync_with_stdio(false);


    cin>>T;


    for (int t=0;t<T;t++)


    {


        cin>>n>>k;


        for (int i=1;i<=n;i++) cin>>a[i];


        for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];


        f[0]=0;


        q[head=tail=0]=0;


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


        {


            #define value(i,j) ((i-j>=k)?(f[j]+s[i]-s[j]-(i-j)*a[j+1]):(oo))


            #define ky(j,k) (f[j]-f[k]+s[k]-s[j]+(j)*a[j+1]-(k)*a[k+1])


            #define kx(j,k) (a[j+1]-a[k+1])


            if (i-k>0)


            {


               while (head<tail


                      &&ky(q[tail-1],q[tail])*kx(q[tail],i-k)


                        >=kx(q[tail-1],q[tail])*ky(q[tail],i-k))


                     tail–;


               q[++tail]=i-k;


            }


            while (head<tail&&value(i,q[head])>value(i,q[head+1])) head++;


            f[i]=value(i,q[head]);


        }


        cout<<f[n]<<endl;


    }


}