- 2024-08-28代码随想录算法训练营第四十三天 | 300.最长递增子序列 , 674. 最长连续递增序列 , 718. 最长重复子数组
目录300.最长递增子序列 思路1.dp[i]的定义2.状态转移方程3.dp[i]的初始化4.确定遍历顺序 5.举例推导dp数组方法一:动态规划方法二:贪心心得收获 674.最长连续递增序列思路动态规划1.确定dp数组(dptable)以及下标的含义2.确定递推公式3.dp数组如何初始化4.
- 2024-08-28算法练习题03:分解质因数
【问题描述】求出区间[a,b]中所有整数的质因数分解,统计一共有多少种不同的分法【输入格式】输人两个整数a和b。【输出格式】输出一行,一个整数,代表区间内质因数分解方法之和。【输入样例】610【输出样例】10【样例说明】6的质因数为2和3,一共有两个。7的质因数有
- 2024-08-28计数 dp 做题记录(日更)
前言因为本人太弱,急需锻炼思维,固从现在起开始着手写计数题,并写下题解分析思路的欠缺。另外本文将长时间更新,所以我准备把它置顶,尽量日更!P3643[APIO2016]划艇2024.8.28简要题意现在有\(n\)个区间,每个区间范围为\([l_i,r_i]\)。现在有\(n\)个元素需要赋值,每个元素的值要
- 2024-08-28力扣热题100_贪心算法_45_跳跃游戏
文章目录题目链接解题思路解题代码题目链接45.跳跃游戏II给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说,如果你在nums[i]处,你可以跳转到任意nums[i+j]处:0<=j<=nums[i]
- 2024-08-28奇怪的花卉(树形DP——最大子树和)
题意小明对数学饱有兴趣,并且是个勤奋好学的学生,总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课,路上见到一个老伯正在修剪花花草草,顿时想到了一个有关修剪花卉的问题。于是当日课后,小明就向老师提出了这个问题:一株奇怪的花卉,上面共连有 N 朵花,共有 N−1 条
- 2024-08-28洛谷P5322 [BJOI2019] 排兵布阵 题解
代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongintdp[20001],a[101][101],s,n,m;signedmain(){ cin>>s>>n>>m; for(intj=1;j<=s;j++){ for(inti=1;i<=n;i++){ cin>>a[i][j]; } } for(inti=1;
- 2024-08-28组合计数学习笔记
组合计数整合8.14:模拟赛组合计数又寄,积累还是不够。8.24:谢拜龚神讲解VJ大专题谢拜龚神括号有关问题P3058[USACO12NOV]BalancedCowBreedsG/S对于括号类问题,研究其合法性时,一个重要的性质就是这一路过来都合法(和栈类似)。套路地,将\(\texttt{(}\)看做\(+1\),\(\textt
- 2024-08-28bnds 8.26
P3117枚举矩形上边界和下边界\(i,j\),然后枚举每一列\(y\),且必须当前列上有\(h\)牛,然后向右枚举直到遇到有g牛的列,更新最大值。注意要离散化一下坐标,再处理一下二维前缀和,时间复杂度\(O(n^3)\)。P3118状压dp,设\(f_i\)表示当前集合为\(i\)时,要连续看多久电影,然后枚举
- 2024-08-28bnds 8.25
P3072因为空洞部分不是很好处理,所以考虑绕着外面搜一圈,所以从最外面的草垛的上一个点开始搜,遇到草就让\(ans\)加1,如果不是草就继续往外面搜,然后剪一下枝,如果一个不是草的点四周八个格子都不是草,那就不往下搜。P3073向周围四个点连一条边权为高度差的绝对值的边,然后最小生成
- 2024-08-28bnds 8.27
P3120朴素dp\(dp_{i,j}\)表示从\((1,1)\)出发到\((i,j)\)的方案数,有\(O(rc)\)的转移,总时间复杂度\(O(r^2c^2)\),通过不了。优化设\(sums\)为\((1,1)\)到\((i-1,j-1)\)的方案数和,\(sumd\)为\((1,1)\)到\((i-1,j-1)\)中,最后一个颜色为\(a[i][
- 2024-08-2814天百题计划第一期
我会记录这\(14\)天(\(\texttt{2024-8-23至2024-9-5}\))做的题目。预计难度范围再\(\texttt{[2000,2500]}\)之间,既可以和博客园的小伙伴们一起学习,也可以让博客园的小伙伴们监督我。\(\texttt{2024-8-23}\)CF1034BLittleCLoves3II\(\texttt{*2000}\)分类讨论\(1\)
- 2024-08-28代码随想录day43 || 300 最长递增子序列,674 最长连续递增子序列,718 最长重复子数组
300最长递增子序列varpath[]intvarresintfunclengthOfLIS(nums[]int)int{ //尝试回溯思路 iflen(nums)==1{ return1 } path=[]int{} res=0 backtracking(nums) returnres}funcbacktracking(nums[]int){ iflen(nums)==0{ iflen(pat
- 2024-08-28洛谷P4163[SCOI2007]排列
洛谷P4163[SCOI2007]排列题意给一个数字串\(s\)和正整数\(d\),统计\(s\)有多少种不同的排列能被\(d\)整除(可以有前导\(0\))。思路考虑状压dp。\(dp_{S,k}\)表示当前已经选定了\(S\)集合(下标)的数,模\(d=k\)的方案数。状态转移方程:\[dp_{S|2^j,(k\times10+s_j)
- 2024-08-28代码随想录训练营 Day42打卡 动态规划 part09 188.买卖股票的最佳时机IV 309. 最佳买卖股票时机含冷冻期 714. 买卖股票的最佳时机含手续费
代码随想录训练营Day42打卡动态规划part09一、力扣188.买卖股票的最佳时机IV给你一个整数数组prices和一个整数k,其中prices[i]是某支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。也就是说,你最多可以买k次
- 2024-08-27CF1810G The Maximum Prefix 题解
Description构造一个长度最多为\(n\)的数组\(a\),其每个元素均为\(1\)或\(-1\)。生成方式如下:选择任意整数\(k\in[1,n]\)作为\(a\)的长度。对于\(\foralli\in[1,k]\),有\(p_i\)的概率设\(a_i=1\),有\(1-p_i\)的概率设\(a_i=-1\)。在数列被生成后,计算\(s_i=a
- 2024-08-278.26 模拟赛(NOIP十三连测 #7)
2024--梦熊&太戈--NOIP十三连测#7【订正】-比赛-梦熊联盟(mna.wang)总结T1基本和CF1245F相同。很快就写完了。T2题意特别难懂,模拟了很长时间后题意还是有些晕,就先放弃了。T3相较于T2看上去简单的多,先冲T3。特殊性质\(A\)有\(50\)分,这可能是正解的关键。尝
- 2024-08-27【题解】「CQOI2014」通配符匹配
【题解】「CQOI2014」通配符匹配https://www.luogu.com.cn/problem/P3167令\(s\)为模式串,\(t\)为文本串。首先有一个显然的的dp是,\(f_{i,j}\)表示模式串的前\(i\)个和文本串的前\(j\)个是否匹配。显然\(O(n^2)\)是过不了的。Motivation:注意到题目限定了通配符
- 2024-08-27蓝桥杯补档
2013省BP8597翻硬币H一排硬币给出初态和终态,每次只能翻转相邻的两枚,求最少多少次用贪心,因为翻转两次相当于没翻,所以最优方案中同一组硬币肯定最多翻转一次,所以翻转顺序无后效性。从前往后翻,只要不一样就把它和它后面的硬币都翻转一次,计数器累加2023省AP9230有奖问答B
- 2024-08-27完全背包问题
完全背包问题有N种物品和一个容量是V的背包,每种物品都有无限件可用。第i种物品的体积是vi,价值是wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。接
- 2024-08-27AT_code_festival_2017_qualc_d - Yet Another Palindrome Partitioning 题解
YetAnotherPalindromePartitioning题解题目大意给出一个字符串,求把这个字符串划分成最少的小段,使每个小段都可以经过字母重组后为回文串。题目分析如果暴力的话,需要DFS段数、每一段的左节点、右节点,以及判断是否为回文串,时间复杂度在\(O(|S|^{|S|})\)左右。但是本
- 2024-08-27记一场 ABC364
于洛谷专栏获得更差的阅读体验。于CSDN获得更一般的阅读体验。赛时ACABCD,赛后补出了E。由于比赛在一个月前,本来已经忘记这场比赛了,直到我看到了:(来自一位超厉害的小学同学神犇)\(364\)?很近的比赛啊,我打过吗?似乎打过?打开题目一看:这不就是斯坦纳树板题吗?但我为什么没印象?
- 2024-08-27收集签名
虽然这道题看起来好像不太能DP的样子,但事实上的确是树形DP,我们考虑每条边怎样被覆盖——而不是被整条路径局限了思维我们依次用x的每个子树y更新x,在子树中枚举i,i>0时,|i|表示有多少个“超级技能”起点向外扩展,i<0时,|i|表示有多少个“超级技能”起点向内扩展,同时子树内有|i|个“超
- 2024-08-27第九章 动态规划Part9
目录任务188.买卖股票的最佳时机IV思路309.买卖股票的最佳时机含冷冻期思路714.买卖股票的最佳时机含手续费思路任务188.买卖股票的最佳时机IV给你一个整数数组prices和一个整数k,其中prices[i]是某支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最
- 2024-08-27dp做题记录
树形dpP3177[HAOI2015]树上染色初看此题时,dp状态很明显是两维,但是合并子树时答案难于统计,然后……就不会了qwq。既然不通,考虑改变dp数组的含义,记\(dp_{i,j}\)表示当前\(i\)的子树中将\(j\)个点染黑对总答案的贡献。但是这样直接计算两点距离就变得更难了,考虑两
- 2024-08-27代码随想录day42 || 188 买卖最佳时机IV,309 买卖最佳时机含冷冻期,714 买卖最佳时机含手续费
188买卖最佳实际IV(k次机会交易)funcmaxProfit(kint,prices[]int)int{ //此题相比买卖两次条件改为买卖k次,所以dp数组行树需要增加为k*2+1 //dp[i][j]表示ifj%2==1第i天第j/3次持有股票获得的收益,j%2==0第i天第j/2次不持有获得的收益 //j%2==1dp[i][j]=