注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]加分二叉树  

2015-08-04 18:10:52|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:区间dp。

Link&Limit


        [洛谷1040]  [codevs1090]
        时间限制:1000ms  空间限制:131072kb

Description


        设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第 i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:
        subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数。
        若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。
        试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;
        (1)tree的最高加分
        (2)tree的前序遍历

Input Format


        第1行:一个整数n(n ≤ 30),为节点个数。
        第2行:n个用空格隔开的整数,为每个节点的分数(分数 ≤ 100)。

Output Format


        第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。
        第2行:n个用空格隔开的整数,为该树的前序遍历。

Sample Input #1


5
5 7 1 2 10

Sample Output #1


145
3 1 2 4 5

        区间dp,设f(i,j)为i~j之间子树的最大得分,那么f(i,j) = max( f(i,k-1) * f(k+1,j) + val(k) )(val是某个点的分数,k是i~j之间的某个点)。最后的答案就是f(1,n).

#include <stdio.h>
int n,a[31],f[31][31],g[31][31];
void printnod(int l,int r)
{
if(l>r) return;
printf("%d ",g[l][r]);
printnod(l,g[l][r]-1);
printnod(g[l][r]+1,r);
}
int main()
{
int i,j,k,l;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i][i] = a[i];
g[i][i] = i;
}
for(l=2;l<=n;l++)
{
for(i=1;i<=n-l+1;i++)
{
j = i+l-1;
if(f[i][j]<a[i]+f[i+1][j])
{
f[i][j] = a[i]+f[i+1][j];
g[i][j] = i;
}
if(f[i][j]<a[j]+f[i][j-1])
{
f[i][j] = a[j]+f[i][j-1];
g[i][j] = j;
}
for(k=i+1;k<j;k++)
{
if(f[i][j]<a[k]+f[i][k-1]*f[k+1][j])
{
f[i][j] = a[k]+f[i][k-1]*f[k+1][j];
g[i][j] = k;
}
}
}
}
printf("%d\n",f[1][n]);
printnod(1,n);
return 0;
}

  评论这张
 
阅读(28)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018