Huster水仙

分类

题解(112)

/ 注册

TA的专栏 16篇文章 0人订阅

16篇文章 911人学习

全部文章（共120篇）

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

最大上升子序列和（不一定连续）思路：统计以s[i]结尾的上升子序列的和sum[i] 分为2类：是否比前面所有元素都小 ①是前面序列对其没有贡献:sum[i]=s[i] ②否前面序列对其有贡献:sum[i]=max(sum[j]+s[i])（需遍历s[i]前面所有元素，保留最大值） #inc...

C++

2023-02-10

1 400

题解 | #拦截导弹#

最长递减子序列（不一定连续）：DP 思路：统计以s[i]结尾的递减子序列的最大长度dp[i] 分为2类：是否比前面所有元素都大 ①是前面序列对其没有贡献:lenth[i]=1 ②否前面序列对其有贡献:dp[i]=max(dp[j]+1 )（需遍历s[i]前面所有元素，保留最大值） #incl...

C++

2023-02-10

0 441

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

简单DP 思路：统计以s[i]结尾的最大子序列和ans[i],多递推一个起始下标即可 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int ...

C++

2023-02-09

1 352

题解 | #最大子矩阵#

矩阵：连续行×连续列每次选定若干连续行之后，将其整体视为一行，就可类比最大子序列和，用DP求解 #include <climits> #include <iostream> using namespace std; const int maxn=101; const int ...

2023-02-09

0 315

题解 | #最大序列和#

简单DP 思路：统计以s[i]结尾的最大子序列和ans[i] 关键找到递归关系： ans[i]： s[i]结尾的最大子序列分为2类：是/否包含s[i-1] ①不包含前面序列对其没有贡献:ans[i]=s[i] ②包含前面序列对其有贡献:ans[i]=ans[i-1]+s[i] #in...

C++

2023-02-09

1 324

题解 | #吃糖果#

斐波那契数列直接递推算出所有答案，每次查找输出即可 #include<iostream> using namespace std; long long ans[21]; void upstairs(int n){ for(int i=0;i<=n;i++){ ...

C++

2023-02-08

0 325

题解 | #N阶楼梯上楼问题#

直接递推算出所有答案，每次查找输出即可 #include<iostream> using namespace std; long long ans[91]; void upstairs(int n){ for(int i=0;i<=n;i++){ long l...

C++

2023-02-08

0 280

题解 | #【模板】拓扑排序#

邻接矩阵+入度队列存放入度为0的结点循环：取出队头，更新相应入度，入度为0的结点入队检查出队元素个数即可判断是否为DAG若对拓扑排序的顺序有要求，将队列加强为优先队列即可 #include <iostream> #include<queue> #include<cstr...

2023-02-07

0 335

题解 | #比赛名次#

拓扑排序（已知为DAG）：邻接矩阵+入度，优先队列保证序号小的排前面 #include <iostream> #include<queue> #include<cstring> #include<vector> using namespace std;...

2023-02-07

0 351

题解 | #I Wanna Go Home#

Dijkstra算法（优先队列优化）注意：we assume that Mr. M starts from city 1 and his target is city 2. 合法路径：1→1,1→2，2→2 非法路径：2→1 距离更新时增加限制：禁止从2转向1 #include<...

C++

2023-02-06

0 323