文和906

分类

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

/ 注册

全部文章（共113篇）

题解 | #[CQOI2007]涂色PAINT#

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

C++ 动态规划区间dp

2021-11-02

2 705

题解 | #小红取数#

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

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

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

C++ 动态规划背包问题

2021-11-01

5 656

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

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

C++ 背包问题动态规划

2021-11-01

1 915

题解 | #字母收集#

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

题解 | #【模板】二维差分#

和#【模板】差分#的思路完全一致。使用一个二位数组sum来记录每一位改变的信息，然后通过求前缀和的形式求出每一位一一对应的改变值。最后将sum中的每一个元素与原始数组arr中对应的元素加起来即可得到结果数组。唯一有区别的地方在记录改变信息以及求前缀和上的操作略微复杂化。这里记录的方式与求前缀和的方式...

C++

2021-10-29

0 549

题解 | #【模板】差分#

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

C++ 动态规划

2021-10-29

0 625

题解 | #【模板】二维前缀和#

思路是用一个二维数组sum来储存(0, 0)到该点所形成的子矩阵中所有数的和。即sum.at(i).at(j)储存着以(0,0)(i,j)为反对角线的矩阵的所有元素的和。当要计算(x1, y1)与(x2, y2)所形成的矩阵中所有元素的和时，只需要用(0, 0)(x2, y2)这个大的矩形，减去(0...

C++ 前缀和动态规划

2021-10-28

0 539

题解 | #abb#

开始时设想使用前缀和的方法，建立一个sum数组，其中sum.at(i)保存的是前i项中abb的个数。按顺序遍历字符串，使用一个二重循环，对每一个字符都统计其在之前出现的次数以及其他字符出现的位置，按照C(2,n)的组合数计算规则可以发现C(2,1), C(2,2), ..., C(2,n)组成的数列...

C++ 后缀和

2021-10-28

2 500

题解 | #【模板】前缀和#

经典前缀和问题。具体做法是在接受输入数字创建数组时，同时创建一个前缀和数组sum，sum.at(i)维护的是数组前i+1项的和(0为首项)。在处理每一组l与r时，直接让前r项的和减去前l项的和在加上第l项的和即可。时间复杂度O(n)，空间复杂度O(n)。 #include <iostream&...

C++ 动态规划前缀和

2021-10-28

0 353