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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

HNOI2008[玩具装箱]  

2010-05-29 10:01:06|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

动态规划,四边形不等式优化,这道题还可以斜率优化。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-5-29

DESCRIPTION:

湖南2008年省选 玩具装箱

*/

#include <stdio.h>

 

class Application

{

      FILE* in;

      FILE* out;

      static const int MAXN=50000;

      int N,L;

      int c[MAXN];

      void print_long_long_int(long long int number)

      {

           if (number>=10) print_long_long_int(number/10);

           fprintf(out,"%d",number%10);

      }

      public:

      Application(const char* input=0,const char* output=0)

                        :in(input?fopen(input,"r"):stdin),

                         out(output?fopen(output,"w"):stdout)

      {

                         fscanf(in,"%d%d",&N,&L);

                         for (int i=0;i<N;i++)

                             fscanf(in,"%d",c+i);

      }

      ~Application()

      {

                    fclose(in);

                    fclose(out);

      }

      int run()

      {

          long long int sum[MAXN+1];

          sum[0]=0;

          for (int i=0;i<N;i++)

              sum[i+1]=sum[i]+c[i];

          long long int f[MAXN+1];

          /*

          f[0]=0;

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

          {

              f[i]=1000000000000000000ll;

              for (int j=0;j<i;j++)

              {

                  long long int x=i-j-1+sum[i]-sum[j]-L;

                  x*=x;

                  if (f[i]>f[j]+x)

                     f[i]=f[j]+x;

              }

          }

          */

          int head,tail;

          int begin[MAXN+1],end[MAXN+1],best[MAXN+1];

          f[0]=0;

          head=tail=0;

          begin[tail]=0;

          end[tail]=N;

          best[tail]=0;

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

          {

              while (end[head]<i) head++;

              int j=best[head];

              long long int x=i-j-1+sum[i]-sum[j]-L;

              f[i]=f[j]+x*x;

              #define value(i,j) \

                      (f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L))

              while (head<tail

                     &&value(begin[tail],best[tail])>=value(begin[tail],i))

                     end[tail-1]=end[tail],tail--;

              int l=begin[tail],r=end[tail]+1;

              while (l+1!=r)

              {

                    int mid=(l+r)>>1;

                    if (value(mid,best[tail])<value(mid,i)) l=mid;

                    else r=mid;

              }

              if (l+1<=end[tail])

              {

                 tail++;

                 begin[tail]=l+1;

                 end[tail]=end[tail-1];

                 best[tail]=i;

                 end[tail-1]=l;

              }

          }

          print_long_long_int(f[N]);

          fprintf(out,"\n");

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

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

历史上的今天

评论

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

页脚

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