静寂旮旯

分类

题解(43)

/ 注册

全部文章（共46篇）

题解 | #旅游#

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

C++ 动态规划

2022-06-05

1 386

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

解题思路：题目规定不能连续相邻两个房间偷，令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 415

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

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

C++ 动态规划

2022-06-03

0 763

题解 | #小红的树#

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

C++ 动态规划

2022-06-03

0 422

题解 | #取数游戏#

解题思路：这题应该是前面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 319

题解 | #[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 355

题解 | #加分二叉树#

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

C++ 动态规划

2022-05-30

1 400

题解 | #能量项链#

解题思路：因为题是一个项圈构成了环，所以使用两倍的长度存储能量项链v[2∗n]v[2*n]v[2∗n]。令dpi,jdp_{i,j}dpi,j表示从下标iii 到下标jjj这一段合并所释放的能量。合并的长度由小到大进行2→n2 \to n2→n。枚举每一段区间比较求得最大值。则有状态转移...

C++ 动态规划

2022-05-27

0 306

题解 | #括号区间匹配#

解题思路：令dpi,jdp_{i,j}dpi,j表示从下标i→ji \to ji→j的最小需要补充的符号数，即区间中不匹配的括号数。初始化 dpi,i=1dp_{i,i} = 1dpi,i=1 则有状态转移方程dpi,j=dpi+1,j−1+match(i,j)，匹配为0，不匹配为2dp_{...

C/C++ C++ 动态规划

2022-05-26

0 456

题解 | #矩阵取数游戏#

解题思路：行之间是独立的，取数时可以单行考虑，令dpl,rdp_{l,r}dpl,r表示当前行从左取的个数和从右取的个数所得到的得分值。则dpl,r from dpl−1,r or dpl,r−1dp_{l,r} \ from \ dp_{l-1,r} ...

Python3 动态规划

2022-05-26

0 281