静寂旮旯

分类

题解(43)

/ 注册

全部文章（共46篇）

题解 | #装箱问题#

解题思路：典型的01背包，转换结果为V−dpVV-dp_VV−dpV,求dpVdp_VdpV的最大值即可。 dpj=max⁡(dpj,dpj−vi+vi)dp_j = \max(dp_j, dp_{j-v_i}+v_i)dpj=max(dpj,dpj−vi+vi) #includ...

C++ 动态规划

2022-05-13

0 274

题解 | #分割等和子集#

解题思路：输入时记录数组和sumsumsum，如果sum%2≠0sum \% 2 \neq 0sum%2=0直接输出false 否则令dpj（01背包）,(0≤j≤sum/2)dp_j（01背包）,(0 \leq j \leq sum/2)dpj（01背包）,(0≤j≤sum/2)，表示...

C++ 动态规划

2022-05-13

0 223

题解 | #兑换零钱#

解题思路：完全背包下加条件，令dpjdp_jdpj 表示第iii种钱下，容量为jjj的背包，考虑dpj=0 or dpj−arri=0dp_j = 0\ or\ dp_{j-arr_i} = 0dpj=0 or dpj−arri=0情况下状态方程：...

C++ 动态规划

2022-05-13

0 364

题解 | #最少的完全平方数#

解题思路：完全背包的变种，令dpjdp_jdpj表示取到第iii个数的容量为jjj的背包（完全平方数之和），那么dpjdp_jdpj的最大值一定是jjj本身（j∗1j*1j∗1），那么从2≤i≤n2 \leq i \leq \sqrt{n}2≤i≤n之间做完全背包，有状态转移方程： dp...

C++ 动态规划

2022-05-13

4 618

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

解题思路：令dp1jdp_{1j}dp1j表示在选取第iii个物品时，容量为jjj的背包，由于是完全背包，有状态方程： dp1j=max⁡(dp1j,dp1j−vi+wi)dp_{1j} = \max(dp_{1j}, dp_{1j-v_i}+w_i)dp1j=max(dp1j,dp1j...

C++ 动态规划

2022-05-13

0 349

题解 | #01背包#

解题思路：普通的01背包，两个dp，dp1,dp2dp_1, dp_2dp1,dp2，令dp1jdp_{1j}dp1j表示在选取物品iii时，容量为jjj的背包。状态方程是： dp1j=max⁡(dp1j,dp1j−vi+wi)dp_{1j} = \max(dp_{1j}, dp_{1j...

C++ 动态规划

2022-05-13

0 250

题解 | #字母收集#

解题思路：建立hash_map {{'l',4},{'o',3},{'v',2},{'e',1}},dp[i][j]=max(dp[i][j−1],dp[i−1][j])+check[v]dp[i][j] = max(dp[i][j-1],dp[i-1][j])+check[v]dp[i][j]...

C++ 动态规划

2022-05-05

0 304

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

解题思路：建立差分二维数组，每一行按照一维差分数组建立cf[i][j]=v[i][j]−v[i][j−1],(1≤i≤n,1≤j≤m)cf[i][j] = v[i][j] - v[i][j-1],(1 \leq i \leq n,1 \leq j \leq m)cf[i][j]=v[i][j]−...

C++ 动态规划

2022-05-05

3 284

题解 | #【模板】差分#

解题思路：分析问题，最直观的办法是暴力，但是在数据量1E5的情况下时间复杂度是达不到要求的。引入差分数组，降低时间复杂度，对于a1,...,ana_1,...,a_na1,...,an构造差分数组cf1,...,cfncf_1,...,cf_ncf1,...,cfn对于cfi=a...

C++ 动态规划

2022-05-05

10 361

题解 | #abb#

解题思路：形式为“abb”，可以用dpidp_idpi来表示第i个字母构成的最大个数，那么dpi = dpi−1 + count(char0,i−1 and chari)(第i个字符和其前面字符构成的“abb”样式的个数）dp_i\ ...

C++ 动态规划

2022-05-04

1 402