【题目大意】
已知一个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的初始值和顺序，这部分详解见代码注释。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<vector> 7 using namespace std; 8 const int MAXN=70+5; 9 const int INF=0x7fffffff; 10 struct node 11 { 12 int data,weight,frequency; 13 bool operator < (const node& x) const 14 { 15 return data<x.data; 16 } 17 }a[MAXN]; 18 int n,K,hash[MAXN]; 19 int f[MAXN][MAXN][MAXN];//f[i][j][w]由i~j组成的子树且每个点的权值都大于等于w的最小总代价 20 21 void init() 22 { 23 scanf("%d%d",&n,&K); 24 for (int i=1;i<=n;i++) scanf("%d",&a[i].data); 25 for (int i=1;i<=n;i++) scanf("%d",&a[i].weight),hash[i]=a[i].weight; 26 for (int i=1;i<=n;i++) scanf("%d",&a[i].frequency); 27 28 sort(hash+1,hash+n+1); 29 sort(a+1,a+n+1); 30 int d=unique(hash+1,hash+n+1)-(hash+1); 31 for (int i=1;i<=n;i++) 32 { 33 a[i].weight=lower_bound(hash+1,hash+d+1,a[i].weight)-hash; 34 } 35 for (int i=2;i<=n;i++) 36 a[i].frequency+=a[i-1].frequency;//求出前缀和 37 38 } 39 40 void dp() 41 { 42 memset(f,0x3f,sizeof(f)); 43 for (int i=1;i<=n+1;i++) 44 for (int w=0;w<=n;w++) f[i][i-1][w]=0; 45 //这个初始化注意一下(!)，下方(i=k/j=k)时用到 46 for (int w=n;w;w--)//根据转移条件，显然w比较大的要先球出来，所以由大到小，放在最外层的循环 47 for (int i=n;i;i--) 48 for (int j=i;j<=n;j++) 49 for (int k=i;k<=j;k++) 50 { 51 if (a[k].weight>=w) f[i][j][w]=min(f[i][j][w],f[i][k-1][a[k].weight]+f[k+1][j][a[k].weight]+(a[j].frequency-a[i-1].frequency)); 52 //因为新增根节点后，每个节点的深度都+1,所以要加上访问的频率和 53 //因为可以取实数，所以后面a[k].weight不需要+1，下面的w也是同理 54 f[i][j][w]=min(f[i][j][w],f[i][k-1][w]+f[k+1][j][w]+(a[j].frequency+K-a[i-1].frequency)); 55 } 56 int ans=INF; 57 for (int i=0;i<=n;i++) 58 ans=min(ans,f[1][n][i]); 59 printf("%d",ans); 60 } 61 62 int main() 63 { 64 init(); 65 dp(); 66 return 0; 67 }