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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

NOI2009[诗人小G/poet]  

2010-05-28 19:08:31|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

动态规划,方程是f[i]=min{f[j]+|sum[i]-sum[j]+i-j-1-L|^P}。

朴素的不能AC,要超时,然后要用四边形不等式优化,优化到O(nlogn)。

恩,四边形不等式优化正在研究中。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-5-27

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

#include <math.h>

 

class Application

{

      FILE* in;

      FILE* out;

      static const int MAXLENGTH=50;

      static const int MAXN=100000;

      static const long long int oo=1000000000000000000ll;

      typedef char string[MAXLENGTH+1];

      int T;

      int N,L,P;

      string s[MAXN+2];

      long long int sum[MAXN+2];

      long long int f[MAXN+2];

      int pre[MAXN+2];

      int top;

      int stack[MAXN+2];

      int head,tail;

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

      void print_long_long_int(long long int number)

      {

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

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

      }

      static long long int abs(long long int n)

      {

             return n>0?n:-n;

      }

      static long long int power(long long int b,long long int p)

      {

             long long int get=1;

             while (p)

             {

                   if (p&1) get*=b;

                   b*=b;

                   p>>=1;

             }

             return get;

      }

      void solve()

      {

           sum[0]=0;

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

               sum[i]=sum[i-1]+strlen(s[i]);

           //f[i]=min{f[j]+|sum[i]-sum[j]+i-j-1-L|^P}

           /*

           f[0]=0;

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

           {

               double min=oo*2;

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

               {

                   double get=f[j]+pow(fabs(sum[i]-sum[j]+i-j-1-L),P);

                   if (get<min)

                   {

                      min=get;

                      pre[i]=j;

                   }

               }

               if (f[pre[i]]+pow(fabs(sum[i]-sum[pre[i]]+i-pre[i]-1-L),P)<oo*2)

               {

                  f[i]=f[pre[i]]+power(abs(sum[i]-sum[pre[i]]+i-pre[i]-1-L),P);

                  if (f[i]>oo) f[i]=oo+1;

               }

               else f[i]=oo+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++;

               pre[i]=best[head];

              

               if (f[pre[i]]+pow(fabs(sum[i]-sum[pre[i]]+i-pre[i]-1-L),P)<oo*2)

               {

                  f[i]=f[pre[i]]+power(abs(sum[i]-sum[pre[i]]+i-pre[i]-1-L),P);

                  if (f[i]>oo) f[i]=oo+1;

               }

               else f[i]=oo+1;

               #define value(now,pre) \

                       f[pre]+pow(fabs(sum[now]-sum[pre]+now-pre-1-L),P)

               while (head<tail

                      &&value(begin[tail],i)<value(begin[tail],best[tail]))

                      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;

               }

               #undef value

           }

           if (f[N]>oo) fprintf(out,"Too hard to arrange\n");

           else

           {

               print_long_long_int(f[N]);

               fprintf(out,"\n");

               stack[top=0]=N;

               while (stack[top])

                     stack[top+1]=pre[stack[top]],top++;

              

               for (int i=top;i>0;i--)

                   for (int j=stack[i]+1;j<=stack[i-1];j++)

                       fprintf(out,"%s%c",s[j],j==stack[i-1]?'\n':' ');

           }

           fprintf(out,"--------------------\n");

          

      }

      public:

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

                        :in(fopen(input,"r")),out(fopen(output,"w"))

      {

                        fscanf(in,"%d",&T);

      }

      ~Application()

      {

                    fclose(in);

                    fclose(out);

      }

      int run()

      {

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

          {

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

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

                  fscanf(in,"%s",s+i);

              solve();

          }

      }

};

 

int main()

{

    static

    Application app("poet.in","poet.out");

    return app.run();

}

 

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

历史上的今天

评论

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

页脚

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