bibibibi

题解

/ 注册

全部文章 / 题解（共21篇）

题解 | #小红的树#

描述给一棵根为111的树，树上部分节点被染色，qqq次询问，每次询问某个节点的子树中有多少被染色的结点思路树形DP模板题，设dp[i]dp[i]dp[i]为节点iii为根的子树有多少节点被染色，初始化时，如果节点iii被染色，则dp[i]=1dp[i]=1dp[i]=1否则为000 转移方程...

C++

2021-11-07

0 747

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

描述有一个体积为VVV的背包，nnn个物体，每个物体的体积和价值分别为viv_ivi和wiw_iwi，每个物品仅可用多次，问: 背包能装的最大价值是多少？将背包装满后的最大价值是多少？思路完全背包的模板题，第一问答案为maxi≤Vdp[i]max_{i \leq V}dp[i]ma...

C++

2021-11-07

0 449

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

描述有一个体积为VVV的背包，nnn个物体，每个物体的体积和价值分别为viv_ivi和wiw_iwi，每个物品仅可用一次，问: 背包能装的最大价值是多少？将背包装满后的最大价值是多少？思路 01背包的模板题，第一问答案为maxi≤Vdp[i]max_{i \leq V}dp[i]ma...

C++

2021-11-07

3 570

题解 | #数位染色#

描述给定一个不超过1e181e181e18的整数，选择101010进制下部分数位的数，使得选择数的和等于没选数的和思路反正只有181818位，直接枚举选择哪些数位暴力就好了，最坏复杂度O(218)O(2^{18})O(218)貌似不用DPDPDP啊代码 #include<bits/...

C++

2021-11-07

1 495

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

描述给定一个n∗mn*mn∗m的矩阵，qqq次询问，每次询问(x1,y1)(x_1,y_1)(x1,y1)为左上角，(x2,y2)(x_2,y_2)(x2,y2)为右下角的子矩阵的和思路二维前缀和的模板题，设矩阵aaa中，左上角为(1,1)(1,1)(1,1)，右下角为(x,y)(...

C++

2021-11-02

0 582

题解 | #abb#

描述给一个长度为nnn的字符串，问有多少个形式为abb的子序列思路一个比较常见的动态规划题目，设dp[i][j]dp[i][j]dp[i][j]表示区间[1,i][1,i][1,i]中以字母jjj为结尾，有多少个形式为ab的子序列，则对于字符串sss最终的答案为∑i∈[1,n]dp[i−1...

C++

2021-11-02

4 455

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

描述给定一个长度为nnn的数组，一共有qqq个询问，每次询问区间[l,r][l,r][l,r]的和思路前缀和的模板题，设sum[n]sum[n]sum[n]表示区间[1,n][1,n][1,n]的和，则每次询问输出sum[r]−sum[l−1]sum[r]-sum[l-1]sum[r]−su...

C++

2021-11-02

0 333

题解 | #nico和niconiconi#

描述给定三个字符串"nico","niconi","niconiconi",分别对应价值a,b,ca,b,ca,b,c，同时给定一个长度为nnn的字符串，选择该字符串中部分子串使得选择的子串的价值最大，每个字符仅能被选一次思路动态规...

C++

2021-11-02

0 404

题解 | #不相邻取数#

描述给定一个长度为nnn的数组，选取一些不相邻的数，使得取出的数最大。思路动态规划的入门题目，设dp[n]dp[n]dp[n]表示仅考虑区间[1,n][1,n][1,n]所能得到的最大结果，对于某个数iii，它可以做的选择为合入区间[1,i−1][1,i-1][1,i−1]的最优结果当中...

C++

2021-11-02

0 377

题解 | #子数组最大连续和#

描述给定一个长度为nnn的数组，输出加和最大的非空子数组的和。思路首先考虑数组中的最大值，如果为负数，则最大子数组为该值，否则答案一定大于0 当最大值为正时，则最大的子数组肯定不为空，则有以下的解法暴力，直接O(n2n^2n2)暴力枚举各个子数组的和，然后输出最大值即可 DP，设dp[i...

C++

2021-11-02

0 367