网站建设前的功能,广州重点场所,seo分析网站,网站的友情链接做多少个比较合适【蓝桥杯冲冲冲】动态规划学习 [NOIP2003 提高组] 加分二叉树 蓝桥杯备赛 | 洛谷做题打卡day24 文章目录 蓝桥杯备赛 | 洛谷做题打卡day24[NOIP2003 提高组] 加分二叉树题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示数据规模与约定思路 题解代码我的一些话 [NOI…【蓝桥杯冲冲冲】动态规划学习 [NOIP2003 提高组] 加分二叉树 蓝桥杯备赛 | 洛谷做题打卡day24 文章目录 蓝桥杯备赛 | 洛谷做题打卡day24[NOIP2003 提高组] 加分二叉树题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示数据规模与约定思路 题解代码我的一些话 [NOIP2003 提高组] 加分二叉树 题目描述 设一个 n n n 个节点的二叉树 tree \text{tree} tree 的中序遍历为 ( 1 , 2 , 3 , … , n ) (1,2,3,\ldots,n) (1,2,3,…,n)其中数字 1 , 2 , 3 , … , n 1,2,3,\ldots,n 1,2,3,…,n 为节点编号。每个节点都有一个分数均为正整数记第 i i i 个节点的分数为 d i d_i di tree \text{tree} tree 及它的每个子树都有一个加分任一棵子树 subtree \text{subtree} subtree也包含 tree \text{tree} tree 本身的加分计算方法如下 subtree \text{subtree} subtree 的左子树的加分 × \times × subtree \text{subtree} subtree 的右子树的加分 subtree \text{subtree} subtree 的根的分数。 若某个子树为空规定其加分为 1 1 1叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为 ( 1 , 2 , 3 , … , n ) (1,2,3,\ldots,n) (1,2,3,…,n) 且加分最高的二叉树 tree \text{tree} tree。要求输出 tree \text{tree} tree 的最高加分。 tree \text{tree} tree 的前序遍历。 输入格式 第 1 1 1 行 1 1 1 个整数 n n n为节点个数。 第 2 2 2 行 n n n 个用空格隔开的整数为每个节点的分数 输出格式 第 1 1 1 行 1 1 1 个整数为最高加分$ Ans \le 4,000,000,000$。 第 2 2 2 行 n n n 个用空格隔开的整数为该树的前序遍历。 样例 #1 样例输入 #1 5
5 7 1 2 10样例输出 #1 145
3 1 2 4 5提示 数据规模与约定 对于全部的测试点保证 1 ≤ n 30 1 \leq n 30 1≤n30节点的分数是小于 100 100 100 的正整数答案不超过 4 × 1 0 9 4 \times 10^9 4×109。
思路
一道入门的区间dp当然根据写法不同你还可以把它归类为树形dp或者记忆化搜索其实都无所谓啦。 作为一道入门题我们完全可以“显然”地做出来但是在这里还是想和大家回顾下动态规划以及区间动规。
Qdp特点是什么 Adp把原问题视作若干个重叠的子问题的逐层递进每个子问题的求解过程都会构成一个“阶段”在完成一个阶段后才会执行下一个阶段。 Qdp要满足无后效性什么叫无后效性 A已经求解的子问题不受后续阶段的影响。
有人觉得dp很抽象那是因为没有一步一步来想直接听别人的结论我们在这里以这道题为例一步一步来推导。
首先我们要做的就是设计状态其实就是设计dp数组的含义它要满足无后效性。 关注这个 左子树*右子树根 我只要知道左子树分数和右子树分数和根的分数已给出不就可以了吗管他子树长什么样 所以我们f数组存的就是最大分数怎么存呢 我们发现子树是一个或多个节点的集合。
题解代码 学会利用新知自己多试试并尝试积攒一些固定解答方案debug以下是题解代码 ~ #includeiostream
#includecstdio
#includecstring
using namespace std;
const int MAXN 50;
typedef long long ll;
ll n;
ll f[MAXN][MAXN], root[MAXN][MAXN];void print(ll l, ll r) {if (l r)return;printf(%lld , root[l][r]);if (l r)return;print(l, root[l][r] - 1);print(root[l][r]1,r);
}int main() {scanf(%lld, n);for (int i 1; i n; i)scanf(%lld, f[i][i]),f[i][i-1]1, root[i][i] i;for (int len 1; len n; len) {for (int i 1; i len n; i) {int j i len;f[i][j] f[i 1][j] f[i][i];//默认它的左子树为空如果有的话这肯定不是最优解root[i][j] i;//默认从起点选根for (int k i 1; k j; k) {if (f[i][j] f[i][k - 1] * f[k 1][j] f[k][k]) {f[i][j] f[i][k - 1] * f[k 1][j] f[k][k];root[i][j] k;}}}}cout f[1][n] endl;print(1, n);return 0;
}我的一些话 今天学习动态规划dp属于比较难的部分需要多动脑多思考思路还是很好掌握的虽然一次性AC有一定难度需要通盘的考虑和理解以及扎实的数据结构基础才能独立写出AC代码。但无论难易大家都要持续做题保持题感喔一起坚持(o´ωo) 如果有非计算机专业的uu自学的话关于数据结构的网课推荐看b站上青岛大学王卓老师的课讲的很细致有不懂都可以私信我喔 总结来说思路很重要多想想多在草稿纸上画画用测试数据多调试debug后成功编译并运行出正确结果真的会感到很幸福 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识之前的博文我都有写欢迎大家关注我翻阅自取哦~ 不管什么都要坚持吧三天打鱼两天晒网无法形成肌肉记忆和做题思维该思考的时候一定不要懈怠今天就说这么多啦欢迎评论留言一起成长
