NOI2009[二叉查找树/treapmod]

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

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();

}

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注