【题目大意】
已知一个treap上每个节点的键值、权值和访问频率。现在可以修改一些节点的权值（可以修改为实数），需要付出k（k为定制）的额外代价。一个treap的总代价=∑（每个节点的访问频率*深度）+额外代价。
*有趣的结论：键值、权值一旦确定，treap是唯一确定的。
【思路】
首先key值是不会变更的，我们按照key值排序，就是按照中序遍历排序。f[i][j][w]代表由i~j组成的子树且每个点的权值都大于等于w的最小总代价。
枚举区间i、j中作为根的k。如果如果wk>=w，就可以不用改根，fi[l][r][k]=min(fi[l][i-1][wk]+fi[i+1][r][wk]+sm[l~i-1]+sm[i+1~r])；还可以一定改根，fi[l][r][k]=min(fi[l][i-1][k]+fi[i+1][r][k]+kk+sm[l~i-1]+sm[i+1~r])。
注意一下，一开始我的想法是“f[i][j][w]代表由i~j组成的子树且每个点的权值都大于w的最小总代价”，但是我没有看见是可以修改为实数的，所以只能用大于等于。
*关注DP的初始值和顺序，这部分详解见代码注释。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int MAXN=+;
const int INF=0x7fffffff;
struct node
{
int data,weight,frequency;
bool operator < (const node& x) const
{
return data<x.data;
}
}a[MAXN];
int n,K,hash[MAXN];
int f[MAXN][MAXN][MAXN];//f[i][j][w]由i~j组成的子树且每个点的权值都大于等于w的最小总代价 void init()
{
scanf("%d%d",&n,&K);
for (int i=;i<=n;i++) scanf("%d",&a[i].data);
for (int i=;i<=n;i++) scanf("%d",&a[i].weight),hash[i]=a[i].weight;
for (int i=;i<=n;i++) scanf("%d",&a[i].frequency); sort(hash+,hash+n+);
sort(a+,a+n+);
int d=unique(hash+,hash+n+)-(hash+);
for (int i=;i<=n;i++)
{
a[i].weight=lower_bound(hash+,hash+d+,a[i].weight)-hash;
}
for (int i=;i<=n;i++)
a[i].frequency+=a[i-].frequency;//求出前缀和 } void dp()
{
memset(f,0x3f,sizeof(f));
for (int i=;i<=n+;i++)
for (int w=;w<=n;w++) f[i][i-][w]=;
//这个初始化注意一下(!)，下方(i=k/j=k)时用到
for (int w=n;w;w--)//根据转移条件，显然w比较大的要先球出来，所以由大到小，放在最外层的循环
for (int i=n;i;i--)
for (int j=i;j<=n;j++)
for (int k=i;k<=j;k++)
{
if (a[k].weight>=w) f[i][j][w]=min(f[i][j][w],f[i][k-][a[k].weight]+f[k+][j][a[k].weight]+(a[j].frequency-a[i-].frequency));
//因为新增根节点后，每个节点的深度都+1,所以要加*问的频率和
//因为可以取实数，所以后面a[k].weight不需要+1，下面的w也是同理
f[i][j][w]=min(f[i][j][w],f[i][k-][w]+f[k+][j][w]+(a[j].frequency+K-a[i-].frequency));
}
int ans=INF;
for (int i=;i<=n;i++)
ans=min(ans,f[][n][i]);
printf("%d",ans);
} int main()
{
init();
dp();
return ;
}