记录编号	578190	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]二叉查找树	最终得分	100
用户昵称	zxhhh	是否通过	通过
代码语言	C++	运行时间	0.355 s
提交时间	2023-02-15 18:30:00	内存使用	5.41 MiB

#include <bits/stdc++.h>

using namespace std;

const int N = 75;
typedef long long ll;

int n, ord[N], t[N], cnt[N][N];
ll dp[N][N][N], k, m[N][N], s[N];

struct node {
	ll a, v, s;
}nodes[N];

bool cmp (node x, node y) { 
	return x.a < y.a;
} 

int main () {
	freopen("treapmod.in", "r", stdin);
	freopen("treapmod.out", "w", stdout);
	memset(m, 0x3f, sizeof(m)); memset(dp, 0x3f, sizeof(dp));
	scanf("%d%lld", &n, &k);
	for (int i = 1;i <= n;i++) scanf("%lld", &nodes[i].a);
	for (int i = 1;i <= n;i++) scanf("%lld", &nodes[i].v);
	for (int i = 1;i <= n;i++) scanf("%lld", &nodes[i].s);
	sort(nodes + 1, nodes + 1 + n, cmp);
	for (int i = 1;i <= n;i++) t[i] = nodes[i].v;
	sort(t + 1, t + 1 + n);
	for (int i = 1;i <= n;i++) ord[i] = lower_bound (t + 1, t + 1 + n, nodes[i].v) - t;
//	for (int i = 1;i <= n;i++) cout << nodes[i].v << " " << ord[i] << endl;
	for (int i = 1;i <= n;i++) {
		s[i] = s[i - 1] + nodes[i].s;
		for (int j = 1;j <= n;j++) {
			cnt[i][j] = cnt[i - 1][j];
			if (ord[i] < j) cnt[i][j]++;
		}
	}
	for (int i = 1;i <= n;i++) {
		for (int j = 0;j <= ord[i] - 1;j++) dp[i][i][j] = nodes[i].s;
		for (int j = ord[i];j <= n;j++) dp[i][i][j] = nodes[i].s;
	}
	for (int l = 2;l <= n;l++) {
		for (int i = 1;i + l - 1 <= n;i++) {
			int j = i + l - 1;
			for (int g = 0;g <= n;g++) {
				for (int z = i;z <= j;z++) {
					ll ls = 0, rs = 0;
					if (ord[z] <= g) {
						if (z > i) ls = dp[i][z - 1][g];
						if (z < j) rs = dp[z + 1][j][g];
						dp[i][j][g] = min(dp[i][j][g], ls + rs + s[j] - s[i - 1]);
					}
					else {
						int x = cnt[j][ord[z]] - cnt[i - 1][ord[z]] - (cnt[j][g + 1] - cnt[i - 1][g + 1]);
						if (z > i) ls = dp[i][z - 1][ord[z]];
						if (z < j) rs = dp[z + 1][j][ord[z]];
						dp[i][j][g] = min(dp[i][j][g], ls + rs + s[j] - s[i - 1] + x * k);
						if (z > i) ls = dp[i][z - 1][g];
						if (z < j) rs = dp[z + 1][j][g];
						dp[i][j][g] = min(dp[i][j][g], ls + rs + s[j] - s[i - 1] + k);
					}
//					if (z > i) ls = dp[i][z - 1];
//					if (z < j) rs = dp[z + 1][j];
//					dp[i][j][g] = min(dp[i][j][g], ls + rs + ad + s[j] - s[i - 1]);
				}
//				cout << i << " " << j << " " << g << " " << dp[i][j][g] << endl; 
			}
				
		}
	}
//	for (int i = 0;i <= n;i++) printf("%lld ", dp[1][n][i]);
	printf("%lld\n", dp[1][n][0]);
	return 0;
}