在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

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

题解 | #[NOIP2006]开心的金明#

还是一个背包问题。只是在这里需要计算的价值变成了每件物品的价格与重要度的乘积。但是由于价格和重要度的乘积的总和较大，所以采用离散化的方式去减少空间。由于没有结果的不需要记录，如果当前选的结果还没有之前没选的大也不用更新。使用map去保存从而减少的空间。 #include&nb...

C++ 动态规划离散化

2023-10-07

1 451

题解 | #[NOIP2005]采药#

本题是一个01背包问题。其中时间其实就相当于背包问题里面的重量。那么可以建立一个二维数组dp[i][j]表示对于第i个药草，时间为j来说它的最大价值。那么它的最大价值有选与不选两种情况，如果不选那么就是上一个药草，时间为j所对应的最大价值、如果选就是上一个药草对于j-a[i].tm的时间的最...

C++ 动态规划

2023-10-07

1 433

题解 | #牛可乐和最长公共子序列#

对于s1的某个位置i，s2的某个位置j。这两个位置之前的最长公共子序列等于=如果这两个位置相同的话就是前面的位置加一。如果不同的话就得比较s1前一位或s2前一位谁比较大了。 #include <bits/stdc++.h> using namespace&nbs...

C++ 动态规划

2023-10-06

1 363

题解 | #最大子串和#

从某一个数字来看，它的最大连续子串和是前面一个数字的最大连续子串和加上它本身，和他本身取较大的那一个。当位于第一个的时候自然就是他自身所以可以实现一个动态规划。故递推式：dp[i] = max(dp[i-1]+dp[i], dp[i])。 //dp[i] = max(...

C++ 动态规划

2023-10-06

1 498

题解 | #滑雪#

本题设dp[i][j]代表从(i,j)这个点出发能够走到的最大距离。但是由于他的上下左右其实也没有被确定，在这里使用记忆化搜索如果上下左右某处没有被确定的话就递归去搜索，如果搜索到的某处为其上下左右的最小值的话就直接返回，如果已经搜索过了也直接返回。此外还要做边界的判断。将每一个点都进行一次...

C++ 动态规划深度优先搜索记忆化搜索

2023-10-06

2 325

题解 | #[NOIP2004]合唱队形#

//从前向后走一遍动态规划计算严格升序序列，从后向前走一遍计算严格升序序列。 //最后再遍历一遍其两者和最大的数，然后拿总数减去就是答案。 #include <bits/stdc++.h> using namespace std; const i...

C++ 动态规划

2023-10-06

2 391

题解 | #[NOIP2003]数字游戏#

本题应该用动态规划才方便，但这里先介绍一种深搜的用法。既然他将一个圆形的分成几部分，为了表示这个圆形我们可以开一个二倍的数组去保存两个相同的序列，这样就可以将首尾给衔接上。那么如何表示圆形序列的分隔呢？在这里可以使用一个now表示当前部分的开头坐标，然后向后去枚举这个部分的末尾下标，...

C++ 深度优先搜索动态规划

2023-10-05

2 397

题解 | #拦截导弹#

本题使用动态规划，用dp数组去保存当前数的最长不上升序列长度。那么后面的下一个数的最长不上升序列长度就是前面大于等于这个数的长度中最大的那一个加一。至于第二问：根据dilworth定理我们知道可划分的最少不上升子序列的数目就是其最长下降子序列的长度。所以求其上升的最长序列即可。 ...

C++ 动态规划

2023-10-05

1 435

题解 | #[NOIP2002]过河卒#

每一个点都有左边或者上边的点变化而来，所以递推式为：dp[i][j] = dp[i-1][j]+dp[i][j-1];。再有就是如果是障碍点那么就需要直接将该点的方案数变成0，马走日的规律就是横坐标差1纵坐标差2或者横坐标差2纵坐标差1。 #include <bits/s...

动态规划

2023-10-04

2 427

题解 | #牛牛国的战争#

//面对每一次的敌人，如果有可以将敌人打到的军队那么选刚好防御力够存活下来的那一个。 //如果能打到敌人但是确是去送死的话，那么选防御力最差的那一个。 //如果不能打倒敌人那么直接宣布失败就可以。 //首先使用结构体数组对其进行相应的排序，然后将攻击力满足的防御力放入multiset（利用set里面...

C++ 贪心 STL

2023-10-04

2 509