吱吱1111111

分类

/ 注册

全部文章（共30篇）

题解 | #打家劫舍(二)# 活用容器

经典问题很多书上都有，比起通常解法用了std的deque容器，可以更方便地操作头尾，不用处理麻烦的下标。 #include <iostream> #include <deque> #include <vector> using namespace std; int...

2024-04-25

1 209

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

先做简单的数据处理，合并相同的数字，然后可以当成偷盗问题 #include <iostream> #include <vector> using namespace std; int main() { //ai<10^4 int n,t,i; ...

2024-04-25

1 197

题解 | #装箱问题# 非背包的做法

不知道为什么要套背包的做法，其实一维dp数组就够了，时间复杂度O(nV)，空间复杂度O(V) #include <iostream> #include <vector> using namespace std; void printa(vector<bool>&a...

2024-04-25

1 263

题解 | #矩阵的最小路径和# 带内存优化的解法

#include <climits> #include <iostream> #include <vector> using namespace std; int main() { int m,n,i,j,curi,previ,t; cin>...

2024-04-25

1 200

题解 | #计算字符串的编辑距离# 带滚动数组内存优化

这道题的滚动数组因为需要参考值，和背包等问题还蛮不一样的，记一下 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { s...

2024-04-24

1 175

暴力解法 | #拦截导弹# 假如不会Dilworth定理

Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度大部分答案都是基于这个，但这个数学定理还蛮冷门的，临时遇到肯定不会做，所以再多写了一个暴力解求最长递减子序列还是用传统dp同时用一系列队列来模拟排队过程策略是拿到一个数字看看已有队列能不能放下它如果有，把它放在队尾数字最小的队...

2024-04-22

1 220

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

#include <climits> #include <vector> #include <iostream> #include <ostream> using namespace std; int main() { int n, t,i,...

2024-04-19

1 190

题解 | #买卖股票的最好时机(三)#dp+滚动数组

没本事理解四个变量版本的代码，所以用了完整的dp，但是用了滚动数组优化内存理论上会有内存消耗/2，但空间复杂度同样O(k)的版本，不过因为代码比较繁琐懒得写了…… #include <climits> #include <vector> #include <iostre...

2024-04-19

1 166

题解 | 过河卒# dp+内存优化

#include <iostream> #include <vector> using namespace std; struct point{ int x; int y; point(int a=0,int b=0):x(a),y(b){} }; ...

2024-04-17

1 185

题解 | #龙与地下城游戏问题# 终点反推 + 内存优化

应该是目前最最优的解，没想出来从起点推到终点的规划方法。如果能够从起点起推，那就可以用滚动数组存储输入数据，进一步优化内存。下面这篇解是从起点开始推的，能通过用例测试，但没有考虑极端情况，即最大收益路线和最低血量路线可能并不重合，可是他的解法里，每一步最低血量的决策跟随了最大收益。https://b...

2024-04-16

1 221