Huster水仙

题解

/ 注册

全部文章 / 题解（共104篇）

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

最大上升子序列和（不一定连续）思路：统计以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 思路：统计以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

题解 | #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

题解 | #最短路径#

比较懒，不想写大数处理（Dijkstra+大数计算）借鉴MST的思想，MST+DFS即可因为本题MST确定之后，最短路径也是唯一确定的 #include<iostream> #include<cstring> #include<cmath> #include...

C++

2023-02-06

0 406

题解 | #最短路径问题#

Dijkstra算法（优先队列优化）结构体增加花费项（cost）增加更新规则（同距离时选花费更少的） #include<iostream> #include<queue> #include<vector> #include<cstring>...

C++ 最短路

2023-02-06

1 477

题解 | #最短路径#

Dijkstra算法（优先队列优化）输入邻接矩阵的边调用迪杰斯特拉算法：每次选取离源点最近的点作为中介，更新到其余的的距离 #include<iostream> #include<vector> #include<cstring> #include<...

C++ 最短路

2023-02-06

0 373