在刷题的单身狗很开心

分类

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

/ 注册

全部文章（共53篇）

题解 | #[NOIP2018]货币系统#

本题是一个完全背包问题，但需要将题目中的问题进行转换。题目中要求最小的等价货币系统的m值。那么其实就是求原有的货币序列里面有哪些数是可以被其他数表示出来的，那么这些数就是不必要存在的数。又有肯定是小的数可以组合成大的数，所以可以首先对序列进行一个排序。然后对于数的排除其实就相当于某个数可以用...

C++ 动态规划完全背包

2023-10-08

1 439

题解 | #Steadily Growing Steam#

这题和失衡天平 (nowcoder.com)这道题很像，都是天平两端需要放东西，那么就把必然需要去维护一个天平两端重量差。但是这道题还有一个技能的使用，使用技能可以将点数加倍。所以这个技能的使用也得需要维护。那么就是维护一个技能的使用次数。 //将手上的牌分成两部分，如果两部分点数相同那么就得...

C++ 动态规划 01背包

2023-10-08

3 410

题解 | #失衡天平#

动态规划问题。确定状态：在某物品要产生的重量差的数值能够放多少重量取决于这个物品会放到天平中的那一边或轻的那一边或不放。有这三种情况之后产生的差值就是上一个物品产生的差值中能够放物品的最大值了。那么递推式为：dp[i][j] = max(dp[i-1][j+a[i]]+a[i], ...

C++ 动态规划

2023-10-08

1 446

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

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

C++ 动态规划离散化

2023-10-07

1 472

题解 | #[NOIP2005]采药#

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

C++ 动态规划

2023-10-07

1 442

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

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

C++ 动态规划

2023-10-06

1 375

题解 | #最大子串和#

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

C++ 动态规划

2023-10-06

1 468

题解 | #滑雪#

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

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

2023-10-06

2 317

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

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

C++ 动态规划

2023-10-06

2 387

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

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

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

2023-10-05

2 397