题解 P1864 【[NOI2009]二叉查找树】

感觉前面的几篇题解讲得不是很清晰啊，那么我根据前面几篇题解的意思（主要是@ 吴逊 的题解），来补一发大家都能看懂的。

性质

拿到这道题，我们首先来发掘性质。

你可以把结点的权值改为任何实数。

输入的权值各不相同。

我们定义一个结点在树中的访问代价为它的访问频度乘以它在树中的深度。（也就是说，访问代价与结点的权值无关。）

以上三点，说明了什么？

这条规则：

但是修改后所有结点的权值必须仍保持互不相同。

无效。

读入的权值不会相同，这就说明：如果我们在最终得到的状态中有两个结点的权值是一样的，那么肯定有一个是修改过来的。而实数完全是可以搞出无限接近但是不相同这种操作的，又因为最终的答案与结点的权值是无关的，所以如果我们把权值相同的那个改成无限接近但不相同，还是可以得到一样的结果。如果最终得到的状态中有多个权值相同，也是同理。所以这条规则有和没有是一样的，没有任何约束力，我们可以直接把它无视掉。

再来发掘一个性质：

学过平衡树的同志们应该很清楚了，题目中给我们的是一棵Treap，而我们修改权值的操作会导致Treap的旋转。我们的目标就是通过恰当的旋转方法使得最后得到的代价总和最小。

而二叉查找树又有一个性质：二叉查找树的中序遍历是其代表的序列从小到大排序的结果。

而无论Treap如何旋转，其都是一棵二叉查找树，因此，无论我们怎么改变数的权值，这棵树的中序遍历还是不会变的。

根据“中序遍历不变”这一原理，我们的DP就可以写出来了。

DP

首先我们要把每个节点的权值给离散化了，方便等下的处理。

然后，我们求出这棵树的中序遍历——也就是把所有节点按照数据值从小到大排序。

1 状态 f[i][j][k]表示将中序遍历中i..j这段节点形成一棵树，要求所有节点的权值\geq k，这棵树的修改代价+访问代价最小是多少

2 转移 我们考虑让哪一个节点做根节点

我们从i到j枚举一个t，表示我们假设让t做这棵树的根节点

那么，我们再来考虑是否要修改t这个节点的权值。

如果不要修改：（前提是t这个点的权值本来就\geq k）

f[i][j][k]=min(f[i][j][k],f[i][t-1][\text{t的权值}]\text{（左子树）}+f[t+1][j][\text{t的权值}]\text{（右子树）}+\text{i..j所有节点的访问频度之和})

注意，那个规则已经无效了，所以我们方程里写的是t的权值而不是t的权值+1

稍微解释一下那个“\text{i..j所有节点的访问频度之和}"：

这个其实是访问代价。

我们知道，访问代价的计算方法是深度\times访问频度

我们可以转化一下，随着我们计算时树的深度步步提高，我们在计算每一深度时将所有深度\geq当前深度的节点的访问频度全部加一遍。最后把每个深度加上的访问频度合起来就是所有节点的深度\times访问频度的总和。我们当前这棵树是由i..j这些节点构成的，而我们现在在第一层，因为所有节点的深度都\geq 1，所以我们加上所有节点的访问频度。等会我们去DPi..t-1子树的时候，就又会再把i..t-1这些结点的访问频度再加一遍。。。以此类推，最后我们就会得到所有节点的深度\times 访问频度之和了。

我好啰嗦啊。

如果要修改：

f[i][j][k]=min(f[i][j][k],f[i][t-1][k]+f[t+1][j][k]+K+\text{i..j所有节点的访问频度之和})

因为整棵树中所有节点的权值都比t要大，而且要大于等于k，所以直接把t的权值修改为k是最优的。

3 初始 除了f[i][i-1][k]=0之外，全部都是inf

4 答案 显然是f[1][n][1]

问：为什么不是f[1][n][0]或者f[1][n][2]之类的东西？

答：f[1][n][0]是可以的，因为0\leq 1，但是f[1][n][2]不一定可行。因为我们在将权值离散化之后权值的范围是[1,n]，你不能强制地让它们都\geq 2。

问：那f[1][n][-1]是不是也可以？

答：可以。但是像f[1][n][0]、f[1][n][-1]这种完全没有必要，会增加计算复杂度。

问：为什么你那么啰嗦？

答：。。。

时间复杂度是O(n^4)，可以通过本题70的数据范围。

代码

啊哈，我的代码看起来会和@吴逊和@18811162081lyh的代码很像。

因为我是看了他们的题解才做出来的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int sum=0;
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){
        sum=sum*10+(c^48);
        c=getchar();
    }
    return sum;
}
int const maxn=75;
struct node{
    int num, quan, pin;
    //数据值  权值 访问频度
}a[maxn];
inline bool cmp(node x,node y){
    return x.num<y.num;
}
int n,K,b[maxn],sum[maxn],f[maxn][maxn][maxn];
signed main(){
    n=read(),K=read();
    for(int i=1;i<=n;i++)
      a[i].num=read();
    for(int i=1;i<=n;i++)
      b[i]=a[i].quan=read();
    for(int i=1;i<=n;i++)
      a[i].pin=read();
    sort(a+1,a+n+1,cmp);//按照数据值从小到大排序，得到中序遍历
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        a[i].quan=lower_bound(b+1,b+n+1,a[i].quan)-b;
        sum[i]=sum[i-1]+a[i].pin;
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n+1;i++)
      for(int k=1;k<=n;k++)
        f[i][i-1][k]=0;
    for(int i=n;i>=1;i--)
      for(int j=i;j<=n;j++)
        for(int k=1;k<=n;k++)
          for(int t=i;t<=j;t++){
              if(a[t].quan>=k) 
                f[i][j][k]=min(f[i][j][k],f[i][t-1][a[t].quan]+f[t+1][j][a[t].quan]+sum[j]-sum[i-1]);
              f[i][j][k]=min(f[i][j][k],f[i][t-1][k]+f[t+1][j][k]+K+sum[j]-sum[i-1]);
          }
    cout<<f[1][n][1]<<endl;
    return 0;
}