静寂旮旯

题解

/ 注册

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

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

解题思路：完全背包的变种，令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 607

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

解题思路：令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

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

解题思路：在输入过程中直接计算，记录从坐标（0，0）到当前坐标（x,y)所构成矩形的和，查询Q(x1,y1)to(x2,y2)=SUM(x2,y2)−SUM(x1−1,y2)−SUM(x2,y1−1)+SUM(x1−1,y1−1)Q_{(x1,y1) to (x2,y2)} = SUM_{(x2...

C++ 动态规划

2022-05-03

2 364

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

解题思路：直接存储前n项的和。对于查询q[l to r]=sum[0 to r]−sum[0 to l−1]q_{[l\ to\ r]} = sum_{[0\ to\ r]} - sum_{[0\ to\ l-1]}q[l t...

C++ 动态规划

2022-05-03

0 229

题解 | #买卖股票的最好时机(四)#

解题思路：分阶段决策，大致可分，0次买卖，1次买卖，k次买卖。决策技巧如上一题。技巧利用-price表示买入价格，决策中使用max取最佳买入价格。如有卖出，假如在i位置卖出，则卖出价格应为在次之前的所有卖出价格中是最优选择即selli=max(sell1−−i−1,pricei+buyi)s...

C++ 动态规划

2022-05-02

4 360