NOIP2003年提高组复赛上机试题 加分二叉树

本文主要是介绍NOIP2003年提高组复赛上机试题 加分二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

• 是否看了题解找思路

1.问题分析

（复习并实战区间dp）

1.1.区间DP

找到[l,r]中的最优解，[1,n]就是答案。
三重循环：
1.区间长度len
2.确定l，从而确定r=l+len-1
3.以k为根节点遍历此时的[l,r]区间。

1.2.对于此题

f[l,r]的含义是所有中序遍历是[l,r]的集合；属性为最大值。
f[l,r]的更新：
以k为root结点：
for(k:l~r){遍历以k为root节点的情况，更新f[l,r]。}
最后在设置path数组储存路径

2.具体代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 35;
typedef long long ll;
ll f[N][N],w[N];
int path[N][N];
void print(int l,int r)
{    if(l>r)return;printf("%d ",path[l][r]);print(l,path[l][r]-1);print(path[l][r]+1,r);
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>w[i];f[i][i]=w[i];path[i][i]=i;}for(int len=2;len<=n;len++)//模板的套用{for(int l=1;l+len-1<=n;l++){int r=l+len-1;for(int k=l;k<=r;k++){ll left = k==l ? 1 : f[l][k-1];ll right= k==r ? 1 : f[k+1][r];if(f[l][r]<left*right+w[k])//递归的难点在于推导出状态转移方程{f[l][r]=left*right+w[k];path[l][r]=k;}}}}cout<<f[1][n]<<endl;print(1,n);return 0;
}

3.总结

一开始的时候写print函数有错误：

void print(int l,int r)
{printf("%d ",path[l][r]);if(l==path[l][r]||r==path[l][r])return;print(l,path[l][r]-1);print(path[l][r]+1,r);
}

递归退出的条件应该是[l,r]不存在，
当l==path[l][r]||r==path[l][r]时，表示递归到了叶结点，还是需要输出的。

这篇关于NOIP2003年提高组复赛上机试题 加分二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---