文和906

分类

未归档(4) 项目笔记(5) 题解(103)

/ 注册

全部文章（共16篇）

题解 | #01串的价值#

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

动态规划

2022-05-05

17 3062

题解 | #旅游#

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

C++ 树形dp 动态规划

2021-11-05

0 344

题解 | #小红的树#

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

C++ 动态规划树形dp

2021-11-04

3 1845

题解 | #合并回文子串#

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

C++ 区间dp 动态规划

2021-11-03

0 420

题解 | #[CQOI2007]涂色PAINT#

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

C++ 动态规划区间dp

2021-11-02

2 483

题解 | #小红取数#

这道题的思路与背包问题有些许相似。转移方程是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 520

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

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

C++ 动态规划背包问题

2021-11-01

5 452

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

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

C++ 背包问题动态规划

2021-11-01

1 728

题解 | #字母收集#

使用一个辅助数组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 405

题解 | #【模板】差分#

因为本题直接解决实现起来不难，故一开始选择直接暴力解法。每次接受l，r，k后，直接遍历数组中的第l个到第r个元素，将其加k。这种做法时间复杂度O(n^2)，空间复杂度O(1)。会在第七个用例(共8个)处超时。由于用例输入数据量过大，无法验证是由于循环逻辑出错导致超时，还是由于算法时间复杂度过高导致超...

C++ 动态规划

2021-10-29

0 466