编程题P15800 选数【题目来源】洛谷[P15800 GESP202603 六级] 选数 - 洛谷【题目描述】给定两个包含n nn个整数的数组a [ a 1 , … , a n ] a[a_1,\dots,a_n]a[a1,…,an]与b [ b 1 , … , b n ] b[b_1,\dots,b_n]b[b1,…,bn]。你需要指定若干下标p 1 ⋯ p k p_1\lt \cdots\lt p_kp1⋯pk1 ≤ k ≤ n 1\leq k\leq n1≤k≤n使得以下条件成立1 ≤ p i ≤ n 1\leq p_i\leq n1≤pi≤n1 ≤ i ≤ k 1\leq i\leq k1≤i≤kp i 1 ≥ p i b p i p_{i1}\geq p_ib_{p_i}pi1≥pibpi1 ≤ i k 1\leq i k1≤ik。你需要在满足以上条件的前提下最大化∑ i 1 k a p k \sum_{i1}^k a_{p_k}∑i1kapk也即最大化数组a aa对应下标的整数之和。【输入】第一行一个正整数n nn表示数组长度。第二行n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an表示数组a aa。第三行n nn个正整数b 1 , b 2 , … , b n b_1,b_2,\dots,b_nb1,b2,…,bn表示数组b bb。【输出】一行一个整数表示在满足下标条件的前提下数组a aa对应下标的整数之和的最大值。【输入样例】4 1 2 3 4 3 3 1 1【输出样例】7【算法标签】《洛谷 P15800 选数》 #动态规划DP# #GESP# #2026#【代码详解】// 40分版本#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,a[N],b[N],ans;// dp[i] 表示以第 i 个活动结尾时能获得的最大价值intdp[N];intlen0;signedmain(){cinn;for(inti1;in;i){cina[i];}for(inti1;in;i){cinb[i];}for(inti1;in;i){// 初始化只选择第 i 个活动dp[i]a[i];// 考虑在 i 之前的活动 jfor(intj1;ji;j){// 检查活动 j 结束后是否可以安排活动 iif(ijb[j]){// 如果可以则尝试从活动 j 转移到活动 idp[i]max(dp[i],dp[j]a[i]);}}}// 找到所有 dp[i] 中的最大值for(inti1;in;i){ansmax(ans,dp[i]);}coutansendl;return0;}// 100分版本#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,a[N],b[N];// dp[i]: 到时间i为止能获得的最大收益不包含在时间i开始的任务intdp[N];signedmain(){cinn;for(inti1;in;i){cina[i];}for(inti1;in;i){cinb[i];}intans0;for(inti1;in;i){// 情况1: 在时间i开始执行任务i// 收益 到时间i为止的最大收益 任务i的收益ansmax(ans,dp[i]a[i]);// 如果执行任务iintfinish_timeib[i];if(finish_timen){// 在任务i结束时更新收益dp[finish_time]max(dp[finish_time],dp[i]a[i]);}// 情况2: 在时间i不执行任何任务// 收益延续到下一个时间点dp[i1]max(dp[i1],dp[i]);}// 注意最终答案不一定是dp[n]因为可能在n时刻之前就已经得到了最大收益// 我们已经在循环中通过ans记录了所有可能的最大值coutansendl;return0;}【运行结果】4 1 2 3 4 3 3 1 1 7P15801 完全二叉树【题目来源】洛谷[P15801 GESP202603 六级] 完全二叉树 - 洛谷【题目描述】给定一棵包含n nn个结点的有根二叉树结点依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n编号根结点编号为1 11。对于结点i ii其左儿子的编号记为l i l_ili右儿子编号记为r i r_iri。特别地如果左儿子不存在则l i 0 l_i0li0如果右儿子不存在则r i 0 r_i0ri0。树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有n nn棵子树中有多少棵子树是完全二叉树。【输入】第一行一个正整数n nn表示有根二叉树结点数量。接下来n nn行每行两个正整数l i , r i l_i,r_ili,ri表示结点i ii的左儿子编号和右儿子编号。【输出】输出一行一个整数表示所有子树中完全二叉树的数量。【输入样例】4 2 3 4 0 0 0 0 0【输出样例】4【解题思路】【算法标签】《洛谷 P15801 完全二叉树》 #树形数据结构# #树形DP# #树的遍历# #GESP# #2026#【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;intn,ans;structtree{intl,r,cnt,dep,flag;}tr[N];voiddfs(intu){intlchildtr[u].l,rchildtr[u].r;// 如果是叶子节点if(lchild0rchild0){tr[u].cnt1;// 节点计数为1tr[u].dep1;// 深度为1tr[u].flag1;// 标记为完全二叉树ans;// 计数加1return;}tr[u].cnt1;// 初始化计数包含当前节点自身// 遍历左子树if(tr[u].l){dfs(tr[u].l);tr[u].cnttr[lchild].cnt;// 累加左子树的节点数tr[u].deptr[lchild].dep1;// 计算深度}// 遍历右子树if(tr[u].r){dfs(tr[u].r);tr[u].cnttr[rchild].cnt;// 累加右子树的节点数tr[u].depmax(tr[u].dep,tr[rchild].dep1);// 更新最大深度}// 处理只有一个子节点的情况if(tr[lchild].dep1tr[rchild].dep0){tr[rchild].flag1;}// 如果左右子树都是完全二叉树if(tr[lchild].flag1tr[rchild].flag1){// 情况1: 左右子树深度相等if(tr[lchild].deptr[rchild].deptr[lchild].cnt(1tr[lchild].dep)-1){tr[u].flag1;// 当前节点是完全二叉树的根ans;}// 情况2: 左子树深度比右子树大1elseif(tr[lchild].deptr[rchild].dep1tr[rchild].cnt(1tr[rchild].dep)-1){tr[u].flag1;// 当前节点是完全二叉树的根ans;}}}intmain(){cinn;for(inti1;in;i){intl,r;cinlr;tr[i].ll,tr[i].rr;}dfs(1);coutansendl;return0;}【运行结果】4 2 3 4 0 0 0 0 0 4
GESP认证C++编程真题解析 | 202603 六级
编程题P15800 选数【题目来源】洛谷[P15800 GESP202603 六级] 选数 - 洛谷【题目描述】给定两个包含n nn个整数的数组a [ a 1 , … , a n ] a[a_1,\dots,a_n]a[a1,…,an]与b [ b 1 , … , b n ] b[b_1,\dots,b_n]b[b1,…,bn]。你需要指定若干下标p 1 ⋯ p k p_1\lt \cdots\lt p_kp1⋯pk1 ≤ k ≤ n 1\leq k\leq n1≤k≤n使得以下条件成立1 ≤ p i ≤ n 1\leq p_i\leq n1≤pi≤n1 ≤ i ≤ k 1\leq i\leq k1≤i≤kp i 1 ≥ p i b p i p_{i1}\geq p_ib_{p_i}pi1≥pibpi1 ≤ i k 1\leq i k1≤ik。你需要在满足以上条件的前提下最大化∑ i 1 k a p k \sum_{i1}^k a_{p_k}∑i1kapk也即最大化数组a aa对应下标的整数之和。【输入】第一行一个正整数n nn表示数组长度。第二行n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an表示数组a aa。第三行n nn个正整数b 1 , b 2 , … , b n b_1,b_2,\dots,b_nb1,b2,…,bn表示数组b bb。【输出】一行一个整数表示在满足下标条件的前提下数组a aa对应下标的整数之和的最大值。【输入样例】4 1 2 3 4 3 3 1 1【输出样例】7【算法标签】《洛谷 P15800 选数》 #动态规划DP# #GESP# #2026#【代码详解】// 40分版本#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,a[N],b[N],ans;// dp[i] 表示以第 i 个活动结尾时能获得的最大价值intdp[N];intlen0;signedmain(){cinn;for(inti1;in;i){cina[i];}for(inti1;in;i){cinb[i];}for(inti1;in;i){// 初始化只选择第 i 个活动dp[i]a[i];// 考虑在 i 之前的活动 jfor(intj1;ji;j){// 检查活动 j 结束后是否可以安排活动 iif(ijb[j]){// 如果可以则尝试从活动 j 转移到活动 idp[i]max(dp[i],dp[j]a[i]);}}}// 找到所有 dp[i] 中的最大值for(inti1;in;i){ansmax(ans,dp[i]);}coutansendl;return0;}// 100分版本#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,a[N],b[N];// dp[i]: 到时间i为止能获得的最大收益不包含在时间i开始的任务intdp[N];signedmain(){cinn;for(inti1;in;i){cina[i];}for(inti1;in;i){cinb[i];}intans0;for(inti1;in;i){// 情况1: 在时间i开始执行任务i// 收益 到时间i为止的最大收益 任务i的收益ansmax(ans,dp[i]a[i]);// 如果执行任务iintfinish_timeib[i];if(finish_timen){// 在任务i结束时更新收益dp[finish_time]max(dp[finish_time],dp[i]a[i]);}// 情况2: 在时间i不执行任何任务// 收益延续到下一个时间点dp[i1]max(dp[i1],dp[i]);}// 注意最终答案不一定是dp[n]因为可能在n时刻之前就已经得到了最大收益// 我们已经在循环中通过ans记录了所有可能的最大值coutansendl;return0;}【运行结果】4 1 2 3 4 3 3 1 1 7P15801 完全二叉树【题目来源】洛谷[P15801 GESP202603 六级] 完全二叉树 - 洛谷【题目描述】给定一棵包含n nn个结点的有根二叉树结点依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n编号根结点编号为1 11。对于结点i ii其左儿子的编号记为l i l_ili右儿子编号记为r i r_iri。特别地如果左儿子不存在则l i 0 l_i0li0如果右儿子不存在则r i 0 r_i0ri0。树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有n nn棵子树中有多少棵子树是完全二叉树。【输入】第一行一个正整数n nn表示有根二叉树结点数量。接下来n nn行每行两个正整数l i , r i l_i,r_ili,ri表示结点i ii的左儿子编号和右儿子编号。【输出】输出一行一个整数表示所有子树中完全二叉树的数量。【输入样例】4 2 3 4 0 0 0 0 0【输出样例】4【解题思路】【算法标签】《洛谷 P15801 完全二叉树》 #树形数据结构# #树形DP# #树的遍历# #GESP# #2026#【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;intn,ans;structtree{intl,r,cnt,dep,flag;}tr[N];voiddfs(intu){intlchildtr[u].l,rchildtr[u].r;// 如果是叶子节点if(lchild0rchild0){tr[u].cnt1;// 节点计数为1tr[u].dep1;// 深度为1tr[u].flag1;// 标记为完全二叉树ans;// 计数加1return;}tr[u].cnt1;// 初始化计数包含当前节点自身// 遍历左子树if(tr[u].l){dfs(tr[u].l);tr[u].cnttr[lchild].cnt;// 累加左子树的节点数tr[u].deptr[lchild].dep1;// 计算深度}// 遍历右子树if(tr[u].r){dfs(tr[u].r);tr[u].cnttr[rchild].cnt;// 累加右子树的节点数tr[u].depmax(tr[u].dep,tr[rchild].dep1);// 更新最大深度}// 处理只有一个子节点的情况if(tr[lchild].dep1tr[rchild].dep0){tr[rchild].flag1;}// 如果左右子树都是完全二叉树if(tr[lchild].flag1tr[rchild].flag1){// 情况1: 左右子树深度相等if(tr[lchild].deptr[rchild].deptr[lchild].cnt(1tr[lchild].dep)-1){tr[u].flag1;// 当前节点是完全二叉树的根ans;}// 情况2: 左子树深度比右子树大1elseif(tr[lchild].deptr[rchild].dep1tr[rchild].cnt(1tr[rchild].dep)-1){tr[u].flag1;// 当前节点是完全二叉树的根ans;}}}intmain(){cinn;for(inti1;in;i){intl,r;cinlr;tr[i].ll,tr[i].rr;}dfs(1);coutansendl;return0;}【运行结果】4 2 3 4 0 0 0 0 0 4
