君鸿

分类

题解(1)

/ 注册

全部文章（共35篇）

题解 | 矩阵取数游戏 | 期间dp，__int128秒杀

解题思路：动态规划注意题目的描述，每次取数时须从每行各取走一个元素，共 n 个，m 次后取完矩阵所有元素，计算m次取数的得分之和。实际上这种取法可以转化下，每次取完一行后再取下一行，得到的结果没有任何差别。因此可以对每一行单独处理，这时就用到了动态规划的思想，这是典型的区间dp问题。由于每次取数必须...

2025-04-01

0 16

题解 | 能量项链

解题思路：动态规划这是一道区间dp的题目。首先第一步是把区间从n扩展到2n，这样就不用尾首循环了。接下来按照区间大小，从小到大循环，先计算小区间的最优解，再计算大区间的最优解。状态转移方程：dp[l][r] = max(dp[l][j] + dp[j][r] + a[l] * a[j] * a[r]...

2025-03-31

0 17

题解 | 小红取数

1、正向思路：动态规划令dp[i]表示：所取之和sum最大，且sum % k = i。具体代码如下。注意每次状态转移之前，要备份一下dp数组。 #include <climits> #include <iostream> #include <vector> usi...

2025-03-28

0 19

题解 | 【模板】01背包 | c++23行代码，第二问红黑树map秒杀

解题思路第一问就是简单的01背包问题，这里不多赘述，有不明白的自己去找资料吧。关键是第二问，问背包恰好装满的情况下，最多能装价值多少的物品。这里的恰好装满是关键。为了避免不必要的空间浪费，我这里使用map进行处理，其中map的任意一个键值对[key, val]表示正好装满体积为key的空间的最大价值...

2025-03-28

1 14

题解 | 最长公共子序列(一) | 动态规划二维压缩到一维

解题思路：动态规划首先使用二维dp，令dp[i][j]表示s1的前i个字符构成的字符串和s2的前j个字符构成的字符串的最长公共子序列。那么有状态转移方程：当s1[i] == s2[j]时，dp[i + 1][j + 1] = dp[i][j] + 1；否则 dp[i + 1][j + 1] = ma...

2025-03-28

0 23

题解 | 最长上升子序列(一) | 贪心+二分

解题思路传统的动态规划思想是，维护一个dp数组，dp[k] 表示以元素 arr[k] 为末尾的最长严格上升子序列的长度。但是这个方法要遍历 k 以前的所有位置，找到满足arr[i] < arr[k]且dp[i]最大的那一个，令dp[k] = dp[i] + 1。时间复杂度为O(n²），这个时间...

2025-03-27

1 20

题解 | 循环汉诺塔

解题思路根据题意，金片只能从一根柱子上顺时针移动到下一个柱子上，而不能反过来移动，因此我们只需要考虑两种情况。1、将n个金片移动到顺时针的下一个柱子上。所需的次数记为 move1[n]2、将n个金牌移动到逆时针的上一个柱子上，相当于是顺时针移动两次。所需的次数记为 move2[n]现在要做的是，推导...

2025-03-26

1 15

题解 | kotori和素因子 | 欧拉筛 + 递归 + 回溯

解题思路1、输入数据，获得数组a，并得到数组a中的最大值，记为maxa。2、使用欧拉筛，计算 2到maxa的所有素数。3、计算数组a中每个元素的素因子列表。4、暴力枚举，递归+回溯，求最优解。思路明确的话，写代码没有什么难度，就不做赘述了，下面详细讨论下素数的筛法。素数的筛法1、埃氏筛法（埃拉托斯特...

2025-03-25

0 18

题解 | 从中序与后序遍历序列构造二叉树 | 简单递归

解题思路简单使用递归即可。1、确定根节点，必然是后序遍历的最后一个元素，以此创建树。2、找到根节点在中序遍历中的位置。3、递归创建左右子树。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNo...

2025-03-25

0 12

题解 | 小红统计区间（hard）| 前缀和+树状数组+离散化

解题思路本题由于原数组a中存在负数，扩大区间范围可能会导致区间和反倒减少，因此不能简单使用滑动窗口。假设已知前缀和数组sum，那么区间和 s[l, r] = sum[r] - sum[l - 1] >= k的必要条件为sum[l - 1] <= sum[r] - k。我们对于每一个右边界...

2025-03-25

0 27