题目大意
有一棵Treap，每个节点有一个互不相同的数据值和权值，以及一个访问频度。一个节点的访问代价为它的访问频度乘以它在树中的深度，整棵树的访问代价定义为所有节点的访问代价之和。节点的权值可以修改为任意实数，每修改一个节点的权值的代价为$K$。任务是修改一些节点的权值，使得整棵树的访问代价与修改代价之和最小。
题目分析
可以修改权值意味着树的形态发生改变，但是无论如何改变，数据值是没有变的，这就意味着中序遍历仍然有序。
我们可以先对数据值进行排序，然后枚举根求解。
发现枚举根后可以转为子问题且具有最优子结构，因此可以考虑使用动态规划解决。
初步分析，设$f[i,j]$表示$i\leftrightarrow j$这段区间表示的子树的最小代价。
如果$k$需要修改权值，还要加上一个$K$。
然而我们发现这样不一定能满足左右区间的根的权值大于当前的$k$的权值。
因此我们还需要把根的权值设进去，事先对权值离散化。
设$f[i,j,k]$表示$i\leftrightarrow j$这段区间根的权值$\ge k$，子树的最小代价。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
struct node {
int data,val,hot;
bool operator < (const node& b) const {
return data<b.data;
}
} a[105];
int n,K,tmp[105],b[105],sum[105],f[105][105][105];
void Discretization(int* a) {
memcpy(b,a,sizeof(b));
sort(a+1,a+n+1);
int cnt=unique(a+1,a+n+1)-a-1;
for(int i=1; i<=n; i++)b[i]=lower_bound(a+1,a+cnt+1,b[i])-a;
}
int main() {
n=Get_Int();
K=Get_Int();
for(int i=1; i<=n; i++)a[i].data=Get_Int();
for(int i=1; i<=n; i++)tmp[i]=Get_Int();
Discretization(tmp);
for(int i=1; i<=n; i++)a[i].val=b[i];
for(int i=1; i<=n; i++)a[i].hot=Get_Int();
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)sum[i]=sum[i-1]+a[i].hot;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
if(a[i].val>=j)f[i][i][j]=a[i].hot;
else f[i][i][j]=a[i].hot+K;
}
for(int k=n; k>=1; k--)
for(int len=2; len<=n; len++)
for(int i=1; i<=n-len+1; i++) {
int j=i+len-1;
f[i][j][k]=0x7fffffff/2;
for(int t=i; t<=j; t++) {
f[i][j][k]=min(f[i][j][k],f[i][t-1][k]+f[t+1][j][k]+sum[j]-sum[i-1]+K);
if(a[t].val>=k)f[i][j][k]=min(f[i][j][k],f[i][t-1][a[t].val]+f[t+1][j][a[t].val]+sum[j]-sum[i-1]);
}
}
printf("%d\n",f[1][n][1]);
return 0;
}
|
