题解 P1864 【[NOI2009]二叉查找树】
ωαηg
2019-10-30 19:57:37
感觉前面的几篇题解讲得不是很清晰啊，那么我根据前面几篇题解的意思（主要是@ [吴逊](https://www.luogu.org/space/show?uid=39597) 的题解），来补一发大家都能看懂的。
----
### 性质
拿到这道题，我们首先来发掘性质。
> 你可以把结点的权值改为任何**实数**。
> 输入的权值**各不相同**。
> 我们定义一个结点在树中的访问代价为它的访问频度乘以它在树中的深度。（也就是说，访问代价与结点的权值**无关**。）
以上三点，说明了什么？
这条规则：
> 但是修改后所有结点的权值必须仍保持互不相同。
**无效。**
读入的权值不会相同，这就说明：如果我们在最终得到的状态中有两个结点的权值是一样的，那么肯定有一个是修改过来的。而实数完全是可以搞出无限接近但是不相同这种操作的，又因为最终的答案与结点的权值是无关的，所以如果我们把权值相同的那个改成无限接近但不相同，还是可以得到一样的结果。如果最终得到的状态中有多个权值相同，也是同理。所以这条规则有和没有是一样的，没有任何约束力，我们可以直接把它无视掉。
再来发掘一个性质：
学过平衡树的同志们应该很清楚了，题目中给我们的是一棵**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$，所以我们加上所有节点的访问频度。等会我们去DP$i..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$的数据范围。
----
### 代码
啊哈，我的代码看起来会和@[吴逊](https://www.luogu.org/space/show?uid=39597)和@[18811162081lyh](https://www.luogu.org/space/show?uid=65531)的代码很像。
~~因为我是看了他们的题解才做出来的。~~
```cpp
#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;
}
```