NOI2009 二叉查找树【区间dp】

【NOI2009】二叉查找树

【问题描述】

　　已知一棵特殊的二叉查找树。根据定义，该二叉查找树中每个结点的数据值
都比它左子树结点的数据值大，而比它右子树结点的数据值小。
另一方面，这棵查找树中每个结点都有一个权值，每个结点的权值都比它的
儿子结点的权值要小。
已知树中所有结点的数据值各不相同；所有结点的权值也各不相同。这时可
得出这样一个有趣的结论：如果能够确定树中每个结点的数据值和权值，那么树
的形态便可以唯一确定。因为这样的一棵树可以看成是按照权值从小到大顺序插
入结点所得到的、按照数据值排序的二叉查找树。
一个结点在树中的深度定义为它到树根的距离加 1。因此树的根结点的深度
为 1。
　　每个结点除了数据值和权值以外，还有一个访问频度。我们定义一个结点在
树中的访问代价为它的访问频度乘以它在树中的深度。整棵树的访问代价定义为
所有结点在树中的访问代价之和。
　　现在给定每个结点的数据值、权值和访问频度，你可以根据需要修改某些
结点的权值，但每次修改你会付出 K 的额外修改代价。你可以把结点的权值改
为任何实数，但是修改后所有结点的权值必须仍保持互不相同。现在你要解决的
问题是，整棵树的访问代价与额外修改代价的和最小是多少？
【输入格式】
输入文件为 treapmod.in。
输入文件第一行包含两个正整数 N 和 K。 N 为结点的个数， K 为每次
修改所需的额外修改代价。
接下来一行包含 N 个非负整数，是每个结点的数据值。
再接下来一行包含 N 个非负整数，是每个结点的权值。
再接下来一行包含 N 个非负整数，是每个结点的访问频度。
所有的数据值、权值、访问频度均不超过 400000。每两个数之间都有一个
空格分隔，且行尾没有空格。
【输出格式】
输出文件为 treapmod.out。
输出文件只有一个数字，即你所能得到的整棵树的访问代价与额外修改代价
之和的最小值。
【样例 1 输入】
4 10
1 2 3 4
1 2 3 4
1 2 3 4
【样例 1 输出】
29
第 6 页共 8 页
【样例 1 说明】
输入的原图是左图，它的访问代价是 1×1+2×2+3×3+4×4=30。最佳的修改方
案是把输入中的第 3 个结点的权值改成 0 ，得到右图，
访问代价是 1×2+2×3+3×1+4×2=19，加上额外修改代价 10，一共是 29。
【子任务】
40%的数据满足 N ≤ 30;
70%的数据满足 N ≤ 50;
100%的数据满足 N ≤ 70, 1 ≤ K ≤ 30000000。

【题解】

　　数据值已经确定了，那么这棵树的中序遍历就已经确定了，我们相当于改变权值来改变深度。

　　而权值可以是任意实数，但是却和答案无关，我们完全可以离散化一下。

　　那么我们设dp[i][j][w]表示以区间[i,j]内的节点为树，根节点都>=w的方案总数。

　　我们通过枚举区间内的根k，可以写出转移方程（sum(i,j)表示[i，j]的访问频率和）。

　　当k>=w时，我们就可以把k之间弄成根，dp[i][j][w]=min(dp[i][k-1][w_k]+dp[k+1][j][w_k]+sum(i,j));

　　也可以把k的权值修改成w,dp[i][j][w]=min(dp[i][k-1][w]+dp[k+1][w]+K+sum(i,j));

　　因为如果直接dp偏序关系不太明确，在实现时可以使用记忆化搜索。（表示一开始直接dp调了一个上午没调出来）

【Code】

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define REP(i,a,b) for(register int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(register int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(register int i=start[(a)];i;i=e[i].next)
inline int read()
{
    int sum=0,p=1;char ch=getchar();
    while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
    if(ch=='-')p=-1,ch=getchar();
    while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
    return sum*p;
}

const int maxn=100;

int n,K;

struct node {
    int a,b,c;
};
node g[maxn];

bool cmp (const node x,const node y)
{
    return x.a<y.a;
}

int Sum(int x,int y)
{
    return g[y].c-g[x-1].c;
}


void init()
{
    int s[maxn];
    n=read();K=read();
    REP(i,1,n)g[i].a=read();
    REP(i,1,n)g[i].b=read(),s[i]=g[i].b;
    REP(i,1,n)g[i].c=read();
    sort(g+1,g+n+1,cmp);
    sort(s+1,s+n+1);
    int cnt=unique(s+1,s+n+1)-(s+1);
    REP(i,1,n)
    {
        REP(j,1,cnt)
        {
            if(g[i].b==s[j]){g[i].b=j;break;}
        }
    }
    REP(i,1,n)g[i].c+=g[i-1].c;
}


ll dp[maxn][maxn][maxn];

void chkmin(ll &a,ll b)
{
    if(a>b)a=b;
}
#define inf 0x7ffffffffff
ll dfs(int l,int r,int k)
{
    if(l>r)return 0;
    if(~dp[l][r][k])return dp[l][r][k];
    ll ans=inf;
    REP(i,l,r)
    {
        chkmin(ans,dfs(l,i-1,k)+dfs(i+1,r,k)+K);
        if(g[i].b>=k)chkmin(ans,dfs(l,i-1,g[i].b)+dfs(i+1,r,g[i].b));
    }
    return dp[l][r][k]=ans+Sum(l,r);
}

void doing()
{
    memset(dp,-1,sizeof(dp));
    //REP(i,1,n)dp[i][i][g[i].b]=Sum(i,i);
    /*REP(len,1,n-1)
    {
        REP(i,1,n-len)
        {
            int j=i+len;
            REP(k,1,Min(i,j))
            {
                REP(l,i,j)
                {
                    int Mn=Min(i,j),z=0;
                    if(Mn==g[l].b)z=0;else z=K;
                    chkmin(dp[i][j][k],dp[i][l-1][Mn]+dp[l+1][j][Mn]+z+Sum(i,j));
                }
            }
        }
        }*/
    cout<<dfs(1,n,1)<<endl;
}
int main()
{
    init();
    doing();
    return 0;
}