bzoj 1564 [NOI2009]二叉查找树区间DP

[NOI2009]二叉查找树

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 906 Solved: 630
[Submit][Status][Discuss]

Description

Input

Output

只有一个数字，即你所能得到的整棵树的访问代价与额外修改代价之和的最小值。

Sample Input

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

Sample Output

HINT

输入的原图是左图，它的访问代价是1×1+2×2+3×3+4×4=30。最佳的修改方案是把输入中的第3个结点的权值改成0，得到右图，访问代价是1×2+2×3+3×1+4×2=19，加上额外修改代价10，一共是29。

Source

题解：这个是个Treap模型应该都知道，然后这题的数据范围应该70吧，题目没写。

　　　正解是dp很难想，dp[l][r][m]表示，区间[l, r]的节点组成的树中的，根节点的权值≥m的最小代价

　　　然后枚举根节点转移。

　　　　（1）将根节点i的权值修改为m，有dp[l][r][m] = dp[l][i - 1][m] + dp[i + 1][r][m] + K

　　　　（2）根节点i的权值≥m时，dp[l][r][m] = dp[l][i - 1][i的权值 + 1] + dp[i + 1][r][i的权值 + 1]

　　　求得dp[l][r][m]最小值后，再给dp[l][r][m]加上[l, r]每个节点的访问频度。

　　　这道题目就是默认了，每个权值都可以取到。

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<queue>
 7 
 8 #define N 87
 9 using namespace std;
10 inline int read()
11 {
12     int x=0,f=1;char ch=getchar();
13     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
14     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 
18 int n,K;
19 struct Node
20 {
21     int v,w,f;
22     friend bool operator<(Node x,Node y)
23     {
24         return x.v<y.v;
25     }
26 }a[N];
27 int f[N][N][N],stk[N],tot;
28 int sum[N];
29 
30 int main()
31 {
32     n=read(),K=read();
33     for (int i=1;i<=n;i++)
34         a[i].v=read();
35     for (int i=1;i<=n;i++)
36         a[i].w=read(),stk[++tot]=a[i].w;
37     for (int i=1;i<=n;i++)
38         a[i].f=read();
39     sort(stk+1,stk+n+1);
40     for (int i=1;i<=n;i++)
41         a[i].w=lower_bound(stk+1,stk+n+1,a[i].w)-stk;
42     sort(a+1,a+n+1);
43     for (int i=1;i<=n;i++)
44         sum[i]=sum[i-1]+a[i].f;
45     memset(f,0x3f,sizeof(f));
46     for (int i=1;i<=n+1;i++)
47         for (int w=0;w<=n;w++)
48             f[i][i-1][w]=0;
49     for (int w=n;w>=1;w--)
50         for (int i=n;i>=1;i--)
51             for (int j=i;j<=n;j++)
52                 for (int k=i;k<=j;k++)
53                 {
54                     f[i][j][w]=min(f[i][j][w],f[i][k-1][w]+f[k+1][j][w]+K+sum[j]-sum[i-1]);
55                     if(a[k].w>=w) f[i][j][w]=min(f[i][j][w],f[i][k-1][a[k].w]+f[k+1][j][a[k].w]+sum[j]-sum[i-1]);
56                 }
57     int ans=0x7f7f7f7f;
58     for (int i=0;i<=n;i++)
59         ans=min(ans,f[1][n][i]);
60     printf("%d
",ans);
61 }