动态规划，看了题解做的，没什么可讲，推荐看这份题解。
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();
}