# bzoj 1564: [NOI2009]二叉查找树

4 10
1 2 3 4
1 2 3 4
1 2 3 4

29

## HINT

``` 1 #include <algorithm>
2 #include <iostream>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cstdio>
6 #include <cmath>
7 using namespace std;
8 typedef long long ll;
9 const int N=75;
10 const ll inf=2e16;
11 ll f[N][N][N];
12 struct node{
13     int x,w,p;
14 }a[N];
15 int b[N];
16 bool comp(const node &pp,const node &qq){
17     return pp.x<qq.x;
18 }
19 int id[N],n;ll sum[N];
20 int midit(int x){
21     int l=1,r=n,mid;
22     while(l<=r){
23         mid=(l+r)>>1;
24         if(b[mid]==x)return mid;
25         if(b[mid]>x)r=mid-1;
26         else l=mid+1;
27     }
28     return 0;
29 }
30 void work()
31 {
32     int D;
33     scanf("%d%d",&n,&D);
34     for(int i=1;i<=n;i++)scanf("%d",&a[i].x);
35     for(int i=1;i<=n;i++)scanf("%d",&a[i].w);
36     for(int i=1;i<=n;i++)scanf("%d",&a[i].p);
37     sort(a+1,a+n+1,comp);
38     for(int i=1;i<=n;i++)b[i]=a[i].w;
39     sort(b+1,b+n+1);
40     for(int i=0;i<=n+1;i++)
41         for(int j=0;j<=n+1;j++)
42             for(int k=0;k<=n+1;k++)
43                 f[i][j][k]=inf;
44     for(int i=1;i<=n;i++)id[i]=midit(a[i].w),sum[i]=sum[i-1]+a[i].p;
45     register int l,r,i,k,j;register ll tmp;
46     for(i=0;i<=n;i++)
47         for(j=0;j<=n;j++)
48             f[i+1][i][j]=0;
49     for(i=n;i>=0;i--){
50         for(k=1;k<=n;k++){
51             for(l=1;l<=n-k+1;l++){
52                 r=l+k-1;
53                 for(j=l;j<=r;j++){
54                     if(id[j]>=i){
55                         tmp=(f[l][j-1][id[j]]+f[j+1][r][id[j]]+sum[r]-sum[l-1]);
56                         if(tmp<f[l][r][i])
57                             f[l][r][i]=tmp;
58                     }
59                     tmp=D+f[l][j-1][i]+f[j+1][r][i]+sum[r]-sum[l-1];
60                       if(tmp<f[l][r][i])
61                           f[l][r][i]=tmp;
62                 }
63             }
64         }
65     }
66     printf("%lld\n",f[1][n][0]);
67 }
68 int main()
69 {
70     freopen("treapmod.in","r",stdin);
71     freopen("treapmod.out","w",stdout);
72     work();
73     return 0;
74 }```

原文作者：PIPIBoss
原文地址: https://www.cnblogs.com/Yuzao/p/7281736.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。