首页 > 代码库 > Vijos 1100 (区间DP)
Vijos 1100 (区间DP)
题目链接: https://vijos.org/p/1100
题目大意：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<j; k++) { if((dp[i][k-1]*dp[k+1][j]+node[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); }}
Vijos 1100 (区间DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。