记录编号	405683	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]二叉查找树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.059 s
提交时间	2017-05-17 11:00:08	内存使用	2.24 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=80;
int n,K,sa[N],rank[N],sum[N],dp[N][N][N];
//dp[i][j][k]表示以[i,j]为子树的根权值排名上取整为k的树最小代价
struct node{int v,r,k;}p[N];
bool cmp(const node &x,const node &y){return x.v<y.v;}
bool comp(int x,int y){return p[x].r<p[y].r;}
int main()
{
	freopen("treapmod.in","r",stdin);
	freopen("treapmod.out","w",stdout);
	scanf("%d%d",&n,&K);
	for (int i=1;i<=n;i++) scanf("%d",&p[i].v);
	for (int i=1;i<=n;i++) scanf("%d",&p[i].r),sa[i]=i;
	for (int i=1;i<=n;i++) scanf("%d",&p[i].k);
	sort(p+1,p+n+1,cmp);
	sort(sa+1,sa+n+1,comp);
	for (int i=1;i<=n;i++) rank[sa[i]]=i,sum[i]=sum[i-1]+p[i].k;
	for (int i=1;i<=n;i++)
	for (int j=i;j<=n;j++)
	for (int k=1;k<=n;k++)
		dp[i][j][k]=1e9;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
		if (rank[i]<j) dp[i][i][j]=K+p[i].k;else dp[i][i][j]=p[i].k;
	for (int L=1;L<n;L++)
	for (int l=1;l+L<=n;l++){
		int r=l+L;
		for (int v=n;v;v--){
			//在k处将区间[l,r]断开
			for (int k=l;k<=r;k++)
			if (rank[k]==v) dp[l][r][v]=min(dp[l][r][v],dp[l][k-1][v]+dp[k+1][r][v]);
				else dp[l][r][v]=min(dp[l][r][v],dp[l][k-1][v]+dp[k+1][r][v]+K);
			dp[l][r][v]+=sum[r]-sum[l-1];
			if (v<n) dp[l][r][v]=min(dp[l][r][v],dp[l][r][v+1]);
		}
	}
	printf("%d\n",dp[1][n][1]);
	return 0;
}