记录编号	412694	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]二叉查找树	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	0.172 s
提交时间	2017-06-09 20:25:04	内存使用	3.51 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long
#define MAXN 75
using namespace std;
 
ll dp[MAXN][MAXN][MAXN], K; //[i, j, p] pi >= p
ll sum[MAXN];
 
struct item {
	int v, f, p;
} A[MAXN];
 
inline bool cmpv(item a, item b) {
	return a.v < b.v;
}
inline bool cmpp(item a, item b) {
	return a.p < b.p;
}
 
int N;
 
int main() {
	freopen("treapmod.in", "rt", stdin);
	freopen("treapmod.out", "wt", stdout);
	
	int i, t;
	scanf("%d%lld", &N, &K);
	for(i=1;i<=N;i++) scanf("%d", &A[i].v);
	for(i=1;i<=N;i++) scanf("%d", &A[i].p);
	for(i=1;i<=N;i++) scanf("%d", &A[i].f);
 
	sort(A+1, A+N+1, cmpp);
	for(i=1;i<=N;i++) A[i].p = i;
 
	sort(A+1, A+N+1, cmpv);
	for(i=1;i<=N;i++) sum[i] = sum[i-1] + A[i].f;
 
	int len, j, k, root;
	memset(dp, 0x3f, sizeof(dp));
 
	for(k=1;k<=N;k++) for(i=0;i<=N;i++) dp[i+1][i][k] = 0;
	for(len=1;len<=N;len++) for(i=1;(j=(i+len-1))<=N;i++) for(k=1;k<=N;k++) {
		for(root=i;root<=j;root++) {
			if(A[root].p >= k) dp[i][j][k] = min(dp[i][j][k], dp[i][root-1][A[root].p] + dp[root+1][j][A[root].p] + sum[j] - sum[i-1]);
			dp[i][j][k] = min(dp[i][j][k], dp[i][root-1][k] + dp[root+1][j][k] + sum[j] - sum[i-1] + K);
		}
	}
	
	printf("%lld", dp[1][N][1]);
}