赫he

分类

题解(3)

/ 注册

全部文章（共55篇）

c++题解 | #兑换零钱#

解释下这种状态转移的思路： dp[i]表示组成i的最少货币数，那对于一种状态dp[k]，就表示组成k的最少货币数状态，它可以来自于两个方面：遍历每个货币，当k>=arr[i]就可以来自于dp[k-arr[i]]这个状态，表示组成{k-arr[i]}的最少货币数再加上arr[i]这种货币1个...

2023-08-15

0 591

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 473

c++题解 | #小红取数#

dp[i][j] 表示前i个数字中取出的数的和，并且对k取余为j的最大值，答案就是dp[n][0]，表示对k取余为0的最大和。整个dp初始化为-1： memset(dp, -1, sizeof(dp)) dp[0][0]初始化为0，表示前0个数取出的数的和是k的倍数的最大值为0； 1、不取a[...

2023-07-27

0 567

题解 | #字母收集#

#include <cstdio> #include <iostream> #include <queue> using namespace std; const int N = 510; int dp[N][N]; int n, m; int main() {...

2023-07-24

0 366

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

二维差分假设a是输入的原矩阵，目标是给定矩形范围，在O(1)时间内将给定矩形范围子矩阵所有值都加上c。可以利用差分的方式。假设b是a的二维差分矩阵，那重点是：a是b的前缀和矩阵。即a[i][j]是b矩阵左上角(1,1)到右下角(i,j)的子矩阵和。那类似于一维差分，当在差分矩阵b上进行加c，对...

2023-07-24

0 366

c++题解 | #【模板】差分#

#include <cstdio> #include <iostream> using namespace std; const int N = 1e5 + 10; typedef long long LL ; LL a[N]; LL d[N]; int n, m; int...

2023-07-21

0 315

c++ 题解 | #abb#

cnt['c']记录字符'c'出现的次数 dp['c']记录以字符'c'结尾的长度为2的子序列的个数，就是"*c"这种形式，两个字符是不一样的，就是叠词的前两个字符。遍历s中的每个字符，假设i=k时，遇到字符x，res = res + dp[x]，就是s[0~k-1]中的答案...

2023-07-21

0 752

很简单：c++题解 | #【模板】二维前缀和#

求二维前缀和矩阵公式：mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1] + 求解给定矩形范围的数字和公式：ans(x1,y1,x2,y2) = mat[x2][y2]-mat[x2][y1-1]-mat[x1-1][y2]+mat[x1-1][...

2023-07-20

1 467

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

很简单，求数组前缀和数组，ans = pres[r]-pres[l-1]，下标从1开始，很方便。 #include <cstdio> #include <iostream> using namespace std; const int N = 1e5+10; typedef ...

2023-07-19

0 276

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

和买卖股票的最好时机(三)思路类似： dp[n][k*2]中的dp[i][kk]：当kk==0、2、4、6...，是第1、2、3、4...次持有状态当kk==1、3、5、7...，是第1、2、3、4...次不持有状态初始化：所有的第一天的任何次持有状态的收益值都是 -p[i]，所有的第一...

2023-07-19

0 513