注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

POJ3709[K-Anonymous Sequence]  

2010-08-22 14:07:26|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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;

    }

}

 

  评论这张
 
阅读(491)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018