静寂旮旯

题解

/ 注册

全部文章 / 题解（共43篇）

题解 | #旅游#

解题思路：说实话，这题是个烂题，完全是做阅读理解的，表达得还不清不楚，很容易让人理解成走走其中最长的分支。按照wa例测试数据猜测，令dpi,0/1dp_{i,0/1}dpi,0/1表示在iii住宿或不住宿的情况。那么有住宿的情况，则一定不住宿离iii距离为1的城市有：dp[i,1]+=dpi...

C++ 动态规划

2022-06-05

1 244

题解 | #打家劫舍(三)#

解题思路：题目规定不能连续相邻两个房间偷，令dpi,0/1dp_{i,0/1}dpi,0/1来表示节点iii为根可以偷到的最大价值，最终结果即max⁡(dp1,0,dp1,1)\max(dp_{1,0},dp_{1,1})max(dp1,0,dp1,1)。假设iii被偷，则有：dpi,1...

C++ 动态规划

2022-06-04

0 292

题解 | #二叉树中的最大路径和#

解题思路二叉树遍历通常利用递归的思想，粗略地写了一版(链接前向星存图），令ansansans表示二叉树中的最大路径和，ansians_iansi表示以nodeinode_inodei为节点的最大路径和，那么ansansans必定是ansians_iansi中的某一个。在遍历的过程中，对于...

C++ 动态规划

2022-06-03

0 618

题解 | #小红的树#

解题思路：所有节点构成一个树，是无回路的无向图，但在这题中只要记录从根节点到叶节点方向的路径，使用链接前向星建立图。对于任一结点 nodei,i∈[1,n]node_i, i \in [1,n]nodei,i∈[1,n],计算以该节点为root的子树中红色节点的个数，只要递归计算出其子树的红色...

C++ 动态规划

2022-06-03

0 280

题解 | #取数游戏#

解题思路：这题应该是前面DP49的简化版，不需要高精度，令dpl,rdp_{l,r}dpl,r表示左侧取lll个，右侧取rrr个的最大值，那么可以得到状态转移方程：dpl,r=max⁡(dpl−1,r+al×bi,dpl,r−1+an−r+1×bi)dp_{l,r} = \max(dp_{l-...

C++ 动态规划

2022-05-31

2 218

题解 | #[CQOI2007]涂色PAINT#

解题思路：根据题目的提示，对于区间[l,r][l,r][l,r]，令dpl,rdp_{l,r}dpl,r表示区间中需要的最少涂色次数，若colorl=colorrcolor_l = color_rcolorl=colorr，则dpl,rdp_{l,r}dpl,r可以由dpl+1,rdp_...

C++ 动态规划

2022-05-31

0 237

题解 | #加分二叉树#

解题思路：问题分析为对于一个中序输入的树，根据规则找出组合积分最大值，即是以输入viv_ivi做为rootrootroot，枚举每一个rootrootroot构成的树形所得到的最大积分。对于每一个构成这棵树的子树也同样符合规则，从节点数2→n2 \to n2→n进行枚举每一个组合选出最大组合...

C++ 动态规划

2022-05-30

1 280

题解 | #装箱问题#

解题思路：典型的01背包，转换结果为V−dpVV-dp_VV−dpV,求dpVdp_VdpV的最大值即可。 dpj=max⁡(dpj,dpj−vi+vi)dp_j = \max(dp_j, dp_{j-v_i}+v_i)dpj=max(dpj,dpj−vi+vi) #includ...

C++ 动态规划

2022-05-13

0 176

题解 | #分割等和子集#

解题思路：输入时记录数组和sumsumsum，如果sum%2≠0sum \% 2 \neq 0sum%2=0直接输出false 否则令dpj（01背包）,(0≤j≤sum/2)dp_j（01背包）,(0 \leq j \leq sum/2)dpj（01背包）,(0≤j≤sum/2)，表示...

C++ 动态规划

2022-05-13

0 140

题解 | #兑换零钱#

解题思路：完全背包下加条件，令dpjdp_jdpj 表示第iii种钱下，容量为jjj的背包，考虑dpj=0 or dpj−arri=0dp_j = 0\ or\ dp_{j-arr_i} = 0dpj=0 or dpj−arri=0情况下状态方程：...

C++ 动态规划

2022-05-13

0 280