普罗列塔丽亚

分类

题解(55)

/ 注册

全部文章（共55篇）

题解 | #最大上升子序列和#

【最长递增子序列】 dp[i]表示“以i结尾”(指必须取num[i])的最长递增子序列长度，因此结果可以累加到dp[n]，直接取dp[n]即可【最大递增子序列和】 dp[i]表示“从0到i”(可以不取num[i])的最大递增子序列和，各自结果独立，因此需要求max...

C++

2022-02-12

2 525

题解 | #最大连续子序列#

没看清题目要求，数字全<0时输出0 0 N-1 maxEnd在每次重新开始时更新即可 maxStart不好记录，倒推即可 #include<iostream> #include<climits> #include<math.h> us...

C++

2022-02-11

0 438

题解 | #最大序列和#

“连续序列”，直接线性dp即可因为只能是连续序列，最值无法传递到末尾所以使用一个maxSum来记录最值 #include<iostream> #include<math.h> using namespace std; int&...

C++

2022-02-11

0 337

题解 | #神奇的口袋#

【01背包问题】从后往前滚动数组【要求凑整数】边界值：[0][0]=1，0枚硬币凑0面值、算一种方案；[0][j]=0 【统计方案数】转移方程：a+b #include<iostream> #include<climits> using n...

C++

2022-02-11

7 604

题解 | #最小邮票数#

用没有状态压缩的二维数组来动态规划第i行考虑加入第i张邮票第j列考虑目标面值为j 用结构体存每个位置凑出的最接近j的面值price和所需的最小张数num 最后看dp[N][M].price是否等于M，输出其num即可比较烦人的是状态转移 #incl...

C++

2022-02-11

0 363

题解 | #Coincidence#

动态规划问题，注意条件转移方程需要分情况讨论字符相等时是从dp[i-1][j-1]转移过来 #include<iostream> #include<math.h> using namespace std; int main(){ ...

C++

2022-02-09

0 281

题解 | #阶乘#

用动态规划的思路去做，一个dp数组一个sum数组递推两次 #include<iostream> using namespace std; int main(){ int dp[...

C++

2022-02-05

0 327

题解 | #大整数排序#

自己整一个排序函数就完了 #include<iostream> #include<string> #include<algorithm> using namespace std; bool cmp(string&n...

C++

2022-02-05

0 287

题解 | #买房子#

题目有点坑，收入是年初更新、房价是年尾更新 #include<iostream> using namespace std; int TryBuy(int n,int k){ ...

C++

2022-02-05

0 426

题解 | #二叉树#

对两个节点分别求其到达根的路径序列，然后再求公共后缀即可 #include<iostream> #include<vector> using namespace std; vector<int> getPath(int&...

C++

2022-02-05

0 331