静寂旮旯

分类

题解(43)

/ 注册

全部文章（共46篇）

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

解题思路：在输入过程中直接计算，记录从坐标（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

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

解题思路：用dp记录收益之和，对于价格贪心只要当天价格比前一天高那么做一次交易，dp加上收益一直到结束，输出，时间复杂度O(n)O(n)O(n),空间复杂度O(1)O(1)O(1)。 #include<bits/stdc++.h> using namespace std; int...

C++ 动态规划

2022-05-02

0 350

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

解题思路：数据量为1E5，那么使用O(n2)O(n^2)O(n2)的解法大概率会超时。分析问题，只要在股票每一天价格中记录最大正向价格差即可，即读入一个价格，如果当前价格比前一天的价格还低则以当前价格暂时做为买入价格，否则记录正向价格差，那么在次过程中的使用一个变量dp记录最大正向价格差即可。...

C++ 动态规划

2022-05-02

2 318

题解 | #跳跃游戏(三)#

解题思路：超时坑点，从前往后推，简单明了的思路，dp[i]表示走到i点的最小步数，那么dp[0] = 1;对于i>0的点，有j0:i−1,j+v[j]>=i,dp[i]=min(dp[j0]:dp[ji−1]+1)j_{0:i-1},j+v[j]>=i,dp[i] = min(...

C++ 动态规划

2022-04-29

1 353

题解 | #跳跃游戏(二)#

解题思路：不能递归了，递归栈真的会炸。递推进行，不能常规地从左往右推，而应该从右往左推，即答案位于dp[0]。先讨论一般情况，dp[i]表达的是此位置能到达n-1位置所能得到的最大分数。那么对于任一位置i有：dp[i]=max(dpi+1:n−1+v[i])dp[i] = max(dp_{i...

C++ 动态规划

2022-04-29

0 341

题解 | #跳跃游戏(一)#

解题思路：普通的dp会超时，在输入过程中直接执行dp，令mx_idx表示当前i下所能到达的最远下标，每次输入取所能到达下标的最大值，假如能到达下标n-1则返回true，但如果在此过程中出现下标i的v为0，而该下标恰好是mx_idx所能达到的最远下标，则不能再继续往下走，可以中断，并返回false...

C++ 动态规划

2022-04-28

0 473

题解 | #删除相邻数字的最大分数#

解题思路：做之前处理下数据，数据的大小是1E4，开一个数组建立一个桶v，对于输入的每一个数据，以数据值做下标，对应的桶数值++即可，再讲输入的数丢入一个set中，习惯操作vector，又将数丢到了v2中，操作的时候只要在这个set中的每一个数依次向后动态规划即可。从左往右考虑，在i行进的过程中...

C++ 动态规划

2022-04-28

1 596

题解 | #打家劫舍(二)#

解题思路：取最大不相邻数之和的变种，原问题可以看作前n-1个数的最大不相邻数之和，和后n-1个数的最大不相邻之和，取两者的最大值即可。 #include<bits/stdc++.h> using namespace std; long long solve(vector<in...

C++ 动态规划

2022-04-28

2 410