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

本题是一个01背包问题。其中时间其实就相当于背包问题里面的重量。 那么可以建立一个二维数组dp[i][j]表示对于第i个药草，时间为j来说它的最大价值。那么它的最大价值有选与不选两种情况，如果不选那么就是上一个药草，时间为j所对应的最大价值、如果选就是上一个药草对于j-a[i].tm的时间的最大价值加上这个药草的价值。在这两种情况下取最大值即可。 #include <bits/stdc++.h> using namespace std; struct Node {     int&...

对于s1的某个位置i，s2的某个位置j。这两个位置之前的最长公共子序列等于=如果这两个位置相同的话就是前面的位置加一。如果不同的话就得比较s1前一位或s2前一位谁比较大了。 #include <bits/stdc++.h> using namespace std; const int maxn = 5000+10; int dp[maxn][maxn]; string s1, s2; int main() {    &nbsp...

从某一个数字来看，它的最大连续子串和是前面一个数字的最大连续子串和加上它本身，和他本身取较大的那一个。当位于第一个的时候自然就是他自身所以可以实现一个动态规划。 故递推式：dp[i] = max(dp[i-1]+dp[i], dp[i])。 //dp[i] = max(dp[i-1]+dp[i], dp[i]) #include <bits/stdc++.h> using namespace std; #define int long long const int&nb...

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

//从前向后走一遍动态规划计算严格升序序列，从后向前走一遍计算严格升序序列。 //最后再遍历一遍其两者和最大的数，然后拿总数减去就是答案。 #include <bits/stdc++.h> using namespace std; const int maxn = 100+10; int N; int a[maxn]; int dp_zuo[maxn]; int dp_you[maxn]; int main() {   &nbsp...

本题应该用动态规划才方便，但这里先介绍一种深搜的用法。 既然他将一个圆形的分成几部分，为了表示这个圆形我们可以开一个二倍的数组去保存两个相同的序列，这样就可以将首尾给衔接上。 那么如何表示圆形序列的分隔呢？在这里可以使用一个now表示当前部分的开头坐标，然后向后去枚举这个部分的末尾下标，要注意这个末尾下标必须给后面的部分留出足够的位置所以是i<=now+n-2-(m-depth)。那么递归这个每一个部分就可以了，但是直接暴力的话会超时所以使用一个结果性的剪枝：当前的数，还比最小值要大并且，加上接下来全为的最大值比最大值要小的话，直接剪枝。 此外在这里面还是用sum数组保...

本题使用动态规划，用dp数组去保存当前数的最长不上升序列长度。那么后面的下一个数的最长不上升序列长度就是前面大于等于这个数的长度中最大的那一个加一。 至于第二问：根据dilworth定理我们知道可划分的最少不上升子序列的数目就是其最长下降子序列的长度。所以求其上升的最长序列即可。 这是O（n^2）复杂度的解法。 #include <bits/stdc++.h> using namespace std; const int maxn = 100000+10; int dp...

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

//面对每一次的敌人，如果有可以将敌人打到的军队那么选刚好防御力够存活下来的那一个。 //如果能打到敌人但是确是去送死的话，那么选防御力最差的那一个。 //如果不能打倒敌人那么直接宣布失败就可以。 //首先使用结构体数组对其进行相应的排序，然后将攻击力满足的防御力放入multiset（利用set里面默认从小到大排序的性质）里面，通过自带的二分查找的函数找到相应的防御力。（这一步直接将攻击力与防御力分开的做法是方便代码编写以及提升速度的关键）。 #include <bits/stdc++.h> using namespace std; #define...

由于有N-1条路，所以最终是一个双端的树形结构。那么可以任意选择一个点作为根节点。 那么深搜的话每向下走一步的话该节点以及子节点的的距离就会减去这一段距离，其余节点会加上这一距离。 也就是说只要顺便选定一个根节点接着向下进行深搜就可以快速得到接下来其他农场的数值。 在这里使用邻接表去存储。当然也看到很多人用链式前向星去存储。都可以。 //由于有N-1条路，所以最终是一个双端的树形结构。那么可以任意选择一个点作为根节点。 //那么深搜的话每向下走一步的话该节点以及子节点的的距离就会减去这一段距离，其余节点会加上这一距离。 //也就是说只要顺便选定一个根节点接着向下进行深搜就可以快速...

题目描述 所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：     +     8468#6633        44445506978 其中#号代表被虫子啃掉的数字。根据算式，我们很容易...

和之前做过的填数独的题目相似，要想DFS的去填写数独的话最关键之处就在于如何进行行与不行的判断。根据游戏规则如果一个数可填那么就需要横和竖以及所在的宫格里面没有相同的数。那么就得采用HASH散列的方式去记录下某一行，某一列以及某一个宫格里面有哪些数。在这里为了方便使用宫格与每一个之间的映射所以提前打表了一个gong_table的数组用于实现映射。 然后这道题复杂在需要求出数值最大的某一种填法，那么最暴力做法就是将所有的填法都搜索出来取最大的那个值。但毫无疑问会超时。 在DFS的搜索树里面越是开头节点少的数最后这棵树也就越小。所以在这里面根据能够填写的数的可能性，先从可能性少的来填起...

将二维地图加上一个钥匙编号变成三维。这样在得到钥匙之后还能去广搜得到下一个钥匙或者救到师父。 在这里面没有明确的结束条件，要保证不走回路就是不能走比他小得路。 #include <bits/stdc++.h> using namespace std; struct Node {     int x, y, z; }; const int maxn = 100+10; char ch[maxn][maxn...