赫he
赫he
全部文章
分类
题解(3)
归档
标签
去牛客网
登录
/
注册
赫he的博客
全部文章
(共53篇)
题解 | #小红的树#
遍历每个颜色red[i]: 如果red[i]=1 (R):将自身以及它的父节点,以及父节点的父节点... 让他们的cnt[父->父]++ 每次询问直接输出cnt[q]即可 #include <iostream> #include <cstring> using nam...
2023-11-03
0
143
题解 | #打家劫舍(三)#
树状dp,一般需要遍历树。方式是深度遍历。 这个题,节点用输入数值的下标来表示,如图所示: f[i][0]表示 以i为根的子树,并且不包括节点i(最大值不包括节点的值)的最大值,该状态可以来自于左右子树(如果存在)的max(f[左子树][0], f[左子树][1])+max(f[右子树][0], ...
2023-09-18
0
143
题解 | #合并回文子串#
#include <iostream> #include <cstring> using namespace std; const int N = 55; const int M = 110; int n; char a[N]; char b[N]; int dp[N][N]...
2023-09-01
0
218
题解 | #加分二叉树#
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 30; int n; ...
2023-08-31
0
367
题解 | #[CQOI2007]涂色PAINT#
题解 定义dp[i][j]是区间str[i~j]上的最少涂色次数。 区间dp的核心思想是由一个个小区间合并成大区间, 所在在dp时应该从长度最短的区间考虑,就是长度为1的区间。 1.长度为1的区间 涂色次数为1 2.长度为2的区间 它可以由两个长度为1的区间合并,这个题的特殊地方在于一次可以涂一个连...
2023-08-31
0
241
题解 | #括号区间匹配#
区间dp dp[i][j]: 区间[i~j]的字符串匹配所插入的字符数最少为dp[i][j] 区间dp,枚举区间长度来遍历i和j。 初始时,区间长度为1时,dp[i][i]=1。长度不为1时,dp[i][j] = inf 当s[i]和s[j]匹配时,dp[i][j] = dp[i+1][j-1] ...
2023-08-19
0
358
题解 | #装箱问题#
#include <iostream> using namespace std; const int N = 2*1e4+10; int dp[N]; //dp[k]表示容量为v时,最大能装多大体积的物品 int nums[31]; int main() { int v,n; ...
2023-08-17
0
183
c++题解 | #分割等和子集#
思路转移:从一个数组中取数字,每个数字只能取一次,问取出的数字之和与未取出的数字之和能否相等。 分析:一个数组中的所有数字分为两部分,问两部分的和能否相等,很明显,如果整个数组的和(s)是奇数,必然不能。当为偶数,则判断是否能在数组中取出一些数,使得它们的和为s/2。 这样问题转移为:容量为s/2的...
2023-08-17
0
249
c++题解 | #兑换零钱#
解释下这种状态转移的思路: dp[i]表示组成i的最少货币数,那对于一种状态dp[k],就表示组成k的最少货币数状态,它可以来自于两个方面: 遍历每个货币,当k>=arr[i]就可以来自于dp[k-arr[i]]这个状态,表示组成{k-arr[i]}的最少货币数再加上arr[i]这种货币1个...
2023-08-15
0
407
c++题解 | #最少的完全平方数#
动态规划:dp[i]表示正整数i最少能由多少个完全平方数组成,答案dp[n]初始化dp[N]=INT_MAX,dp[0]=0转移方程:dp[i+j*j] = min(dp[i+j*j] , dp[i]+1)数字x最少组成个数来自自己本身,或者数i,并且i满足:x=i+j*j #include <...
2023-08-14
0
327
首页
上一页
1
2
3
4
5
6
下一页
末页