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

return 0;

}

};

int main()

{

Application app(“treapmod.in”,“treapmod.out”);

return app.run();

}