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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

NOI2009[二叉查找树/treapmod]  

2010-05-30 12:44:07|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

动态规划,看了题解做的,没什么可讲,推荐看这份题解

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-5-30

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <algorithm>

using std::sort;

using std::min;

 

class Application

{

      FILE* in;

      FILE* out;

      static const int MAXN=70;

      typedef struct{int key,weight,p;} Node;

      int N,K;

      Node node[MAXN];

      static bool less_weight(const Node& a,const Node& b)

      {

             return a.weight<b.weight;

      }

      static bool less_key(const Node& a,const Node& b)

      {

             return a.key<b.key;

      }

      int dp(int i,int j,int w)

      {         

          static int f[MAXN][MAXN][MAXN+1];

          static bool calced[MAXN][MAXN][MAXN+1];

          if (i>j) return 0;

          if (!calced[i][j][w])

          {

             calced[i][j][w]=true;

             f[i][j][w]=~(1<<31);

             int get;

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

             {

                 get=dp(i,k-1,w)+dp(k+1,j,w)+sum(i,j)+K;

                 f[i][j][w]=min(f[i][j][w],get);                 

                 if (node[k].weight>=w)

                 {

                    int _w=node[k].weight;

                    get=dp(i,k-1,_w)+dp(k+1,j,_w)+sum(i,j);

                    f[i][j][w]=min(f[i][j][w],get);

                 }

             }

          }

          return f[i][j][w];

      }

      int sum(int i,int j)

      {

          static bool calced;

          static int f[MAXN+1];

          if (!calced)

          {

             calced=true;

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

                 f[i+1]=f[i]+node[i].p;

          }

          return f[j+1]-f[i];

      }

      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,&K);

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

                             fscanf(in,"%d%",&node[i].key);

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

                             fscanf(in,"%d",&node[i].weight);

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

                             fscanf(in,"%d",&node[i].p);

      }

      ~Application()

      {

                    fclose(in);

                    fclose(out);

      }

      int run()

      {

          sort(node,node+N,less_weight);

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

              node[i].weight=i+1;

          sort(node,node+N,less_key);

         

          int answer=min(dp(0,N-1,1),dp(0,N-1,0));

          fprintf(out,"%d\n",answer);

          return 0;

      }

};

 

int main()

{

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

    return app.run();

}

 

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

历史上的今天

评论

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

页脚

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