博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Vijos 1100 (区间DP)
阅读量:5882 次
发布时间:2019-06-19

本文共 1519 字,大约阅读时间需要 5 分钟。

题目链接

题目大意:NOIP著名的加分二叉树。给出一棵树的中序遍历,加分规则左子树*右子树+根。空子树分数为1。问最大加分的树结构,输出树结构的先序遍历。

解题思路

先从小的问题看起。

对于一棵子树,只要知道根是啥,就能轻松求出这棵子树的加分情况。

那么就变成枚举根的区间DP问题。

由于要输出先序遍历,则用m[i][j]记录在i~j区间选择的根。

 

区间DP边界:

①一个点情况:即无左右子树,dp[i][i]=node[i],m[i][i]=i.

②两个点情况,即无右子树。dp[i][i+1]=node[i]+node[i+1];m[i][i+1]=i。

注意为什么DP边界是两种情况,是因为区间DP枚举中间分割点时,是按照常规处理左区间和右区间的,以上两种情况,左右区间都是有问题的。

所以需要特别预处理。

 

区间DP:

推荐先枚举区间间隔p的写法,这里直接从p=2开始计算。p=0,p=1已经预处理。

对于dp[i][j],则根k的范围(i+1,j),按照规则写方程就行了。m[i][j]=k,记录每个区间的根。

则最后ans=dp[1][n]。

递归打印方案,先序遍历是根左右,不要打错了。

 

#include "cstring"#include "cstdio"#include "cstring"int dp[31][31],m[31][31],node[31];void print(int i,int j){    printf("%d ",m[i][j]);    if(i<=m[i][j]-1) print(i,m[i][j]-1);    if(m[i][j]+1<=j) print(m[i][j]+1,j);}int main(){    //freopen("in.txt","r",stdin);    int n;    while(scanf("%d",&n)!=EOF)    {        memset(dp,0,sizeof(dp));        for(int i=1; i<=n; i++) scanf("%d",&node[i]);        for(int i=1; i<=n; i++)        {            dp[i][i]=node[i];            m[i][i]=i;            dp[i][i+1]=node[i]+node[i+1];            m[i][i+1]=i;        }        for(int p=2; p<=n; p++)        {            for(int i=1; i<=n; i++)            {                int j=i+p;                if(j>n) break;                dp[i][j]=1;                for(int k=i+1; k
dp[i][j]) { dp[i][j]=dp[i][k-1]*dp[k+1][j]+node[k]; m[i][j]=k; } } } } printf("%d\n",dp[1][n]); print(1,n); }}

 

转载地址:http://topix.baihongyu.com/

你可能感兴趣的文章
cocos2d中CCAnimation的使用(cocos2d 1.0以上版本)
查看>>
【吉光片羽】短信验证
查看>>
MacBook如何用Parallels Desktop安装windows7/8
查看>>
gitlab 完整部署实例
查看>>
GNS关于IPS&ASA&PIX&Junos的配置
查看>>
影响企业信息化成败的几点因素
查看>>
SCCM 2016 配置管理系列(Part8)
查看>>
struts中的xwork源码下载地址
查看>>
ABP理论学习之仓储
查看>>
我的友情链接
查看>>
Tengine新增nginx upstream模块的使用
查看>>
CentOS图形界面和命令行切换
查看>>
HTML5通信机制与html5地理信息定位(gps)
查看>>
汽车常识全面介绍 - 悬挂系统
查看>>
加快ALTER TABLE 操作速度
查看>>
学习笔记之软考数据库系统工程师教程(第一版)
查看>>
PHP 程序员的技术成长规划
查看>>
memcached 分布式聚类算法
查看>>
jquery css3问卷答题卡翻页动画效果
查看>>
$digest already in progress 解决办法——续
查看>>