首页 > 代码库 > NOI2009 二叉查找树 【区间dp】
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][wk]+dp[k+1][j][wk]+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 0x7ffffffffffll 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;}
NOI2009 二叉查找树 【区间dp】