文和906

题解

未归档(4) 项目笔记(5)

/ 注册

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

题解 | #01串的价值#

动态规划解法。使用val数组来记录前i个元素的最大价值。初始化val[0]=1。从第二项开始遍历字符串。对每一项，其价值最小为上一项价值+1，如221。所以先将其价值预设为最小值，val[i]=val[i-1]+1。并设置一个计数，cnt=1。从i-1项开始，从后向前遍历字符串。当遇到与i...

动态规划

2022-05-05

17 3039

题解 | #游历魔法王国#

读完题后感觉是比较常见的树的dfs问题。但是看完输入格式之后有点懵，这种奇怪的输入格式虽然也能用邻接表或邻接矩阵存储，但是很别扭。看了评论区大神的解答后才知道链式前向星这种数据结构，这道题过于适合使用链式前向星来解答，很难不怀疑出题者是按照链式前向星来输入的。主要难点就在链式前向星的使用上。关于...

C++ 深度优先搜索链式前向星

2022-04-15

0 322

题解 | #旅游#

从题目中给出的n个结点n-1条边可知输入的是一棵树，可知是树形DP。简历二维dp数组，dp[i][0]表示在第i个结点住宿时能旅游的最长天数，dp[i][1]表示不在第i个结点住宿时能旅游的最长天数。第二维只有0和1两个取值，表示是否在第i个结点住下。在计算dp数组时，采用深度优先遍历。为此，使用邻...

C++ 树形dp 动态规划

2021-11-05

0 335

题解 | #小红的树#

开始时考虑的是暴力解法。构建树的过程就不说了。这里有一点需要注意，题目中的树并非二叉树，只是一个无环连通图，所以树节点中只能设定保存父节点的指针。在每次统计节点x的子节点中红色节点的个数时，使用一个辅助队列，开始时将x结点入队。进入循环后，查看队头结点是否为红色，然后遍历整棵树的所有结点，当遇到父节...

C++ 动态规划树形dp

2021-11-04

3 1785

题解 | #合并回文子串#

区间DP问题。与涂色问题大同小异，但如果想不明白就会觉得这两者有很大区别。用一个四维数组dp[l1][r1][l2][r2]表示从第一个字符串中取l1到r1，从第二个字符串中取l2到r2是否能组成回文字符串，若不能则为0，能则为1。状态转移方程分4种情况，因为字符串Ａ、Ｂ有四种情况可以组成会问字符串...

C++ 区间dp 动态规划

2021-11-03

0 407

题解 | #[CQOI2007]涂色PAINT#

区间dp。我也对这类题型比较陌生，只能写下自己浅薄的理解，欢迎大佬指教。开始时对这道题没什么头绪，查阅了一些资料后写下了这段程序。不敢说已经完全理解，只记录下我写代码时的思路。这里dp数组记录的是将第i个位置到第j个位置涂色的最少次数。初始化dp时，由于是求最小值，所以先将数组中所有元素初始化为一个...

C++ 动态规划区间dp

2021-11-02

2 455

题解 | #小红取数#

这道题的思路与背包问题有些许相似。转移方程是df[i][(j+arr[i])%k]=max(df[i-1][j]+arr[i],df[i-1][(j+arr[i])%k])。其中df[i][j]表示添加第i个数时对k取模得j的最大和。在实现时考虑是否能像背包问题一样，仅使用一维数组，通过遍历的顺序来...

C++ 动态规划

2021-11-02

4 499

题解 | #【模板】完全背包#

这道题在弄懂01背包问题后基本没有难度。基本思路与01背包问题相同。唯一不同的是，题目中的物品可以重复加入，而01背包问题中要避免物品重复加入。在01背包问题中，避免重复添加一件物品是通过逆序遍历来实现的，而在本题中要包含重复添加一件物品的情况，只需将逆袭改为正序遍历即可。附01背包问题题解 #i...

C++ 动态规划背包问题

2021-11-01

5 438

题解 | #【模板】01背包#

经典01背包问题。解题思路比较常规。用辅助数组res存储容积为i时能装入物品的最大价值。对物品进行遍历，每次遍历中都逆序更新res，转移方程为res[j]=max(res[j-v[i]]+p[i],res[j])。最终res[v]即为要求的容积为v时所能装入物品的最大价值。这道题设置了两问，解题上有...

C++ 背包问题动态规划

2021-11-01

1 715

题解 | #字母收集#

使用一个辅助数组sum记录从起点走到当前位置的最大值，即sum.at(i).at(j)表示从(0,0)走到(i,j)的所有路径中的最大值。最后返回sum.at(n-1).at(m-1)即为走完整个矩阵的最大值。由于遍历了存储矩阵的二维数组，时间复杂度为O(nm)。由于使用了sum辅助数组，空间复杂度...

C++ 动态规划

2021-10-29

0 390