题目训练网址（密码hpuacm）： https://vjudge.net/contest/245538 其实我之前的博文已经提到过一次记忆化搜索关于01背包的： 文章链接 对于记忆化搜索其实很好理解。就是每次DFS得到的结果用一个用来记忆值的数组保存。直接来看一道题目更好理解。                                                 滑雪 Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组...

题目训练（密码hpuacm）：https://vjudge.net/contest/244922 背包问题有 部分背包 01背包 完全背包 多重背包 部分背包是一种可分割的背包，就是一个背包我们可以只取它的部分。那么给出一组物品的价值和重量，怎么选才能让背包装的价值最大呢？很简单，选性价比最高的，即优先选择的是单位重量价值（v[i] / w[i]）最高的那个。 01背包就很熟悉了，就是给出一系列的物品，每个物品只有选和不选两个状态，故称为01背包。 完全背包则是在01背包的基础上，每个物品可以挑选任意件，问背包能装的最大价值。 多重背包则是每个物品有c[i]个，每个物品能选0 - c[i] 个...

题目训练（密码hpuacm）：https://vjudge.net/contest/244922 背包问题有 部分背包 01背包 完全背包 多重背包 部分背包是一种可分割的背包，就是一个背包我们可以只取它的部分。那么给出一组物品的价值和重量，怎么选才能让背包装的价值最大呢？很简单，选性价比最高的，即优先选择的是单位重量价值（v[i] / w[i]）最高的那个。 01背包就很熟悉了，就是给出一系列的物品，每个物品只有选和不选两个状态，故称为01背包。 完全背包则是在01背包的基础上，每个物品可以挑选任意件，问背包能装的最大价值。 多重背包则是每个物品有c[i]个，每个物品能选0 - c[i] 个...

                                                    最大子段和   N个整数组成的序列a11,a22,a33,…,ann， 求该序列如aii+ai+1i+1+…+ajj的连续子段和的最大值。当所给的整数均为负数时和为0。 例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。 Input 第1行：整数序列的长度N（2 <= N <= 50000)  第2 - N + 1行：N个整数（-10^9 <= Aii <= 10^9） Output 输出最大子段和。 Sample Input  6...

                                                    最大子段和   N个整数组成的序列a11,a22,a33,…,ann， 求该序列如aii+ai+1i+1+…+ajj的连续子段和的最大值。当所给的整数均为负数时和为0。 例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。 Input 第1行：整数序列的长度N（2 <= N <= 50000)  第2 - N + 1行：N个整数（-10^9 <= Aii <= 10^9） Output 输出最大子段和。 Sample Input  6...

                                                    钱币兑换问题   在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768。 Output 对应每个输入，输出兑换方法数。 Sample Input  2934 12553 Sample Output  718831 13137761 先看代码，着重看以下递推式的循环  #include <bits/stdc++.h> using namespace std; typedef long ...

                                                    钱币兑换问题   在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768。 Output 对应每个输入，输出兑换方法数。 Sample Input  2934 12553 Sample Output  718831 13137761 先看代码，着重看以下递推式的循环  #include <bits/stdc++.h> using namespace std; typedef long ...

题目链接（密码hpuacm）： 2018HPU暑期集训—动态规划入门 看故事了解动态规划思想： click here！！！ 求解动态规划问题求到最后无非就三种方法，见我之前的博文用三中方法详细讲解了01背包问题。 第一种递归搜索法：  https://blog.csdn.net/hpu2022/article/details/80741681 第二种递归搜索法+记忆： https://blog.csdn.net/hpu2022/article/details/80745884 第三种递推式法，此种方法最难理解，初学者可以从上两种的方法来理解： https://blog.csdn.net/hpu...

题目链接（密码hpuacm）： 2018HPU暑期集训—动态规划入门 看故事了解动态规划思想： click here！！！ 求解动态规划问题求到最后无非就三种方法，见我之前的博文用三中方法详细讲解了01背包问题。 第一种递归搜索法：  https://blog.csdn.net/hpu2022/article/details/80741681 第二种递归搜索法+记忆： https://blog.csdn.net/hpu2022/article/details/80745884 第三种递推式法，此种方法最难理解，初学者可以从上两种的方法来理解： https://blog.csdn.net/hpu...

题目训练网址（密码hpuacm）：https://vjudge.net/contest/243680   先说一下归并排序求逆序数法 什么事逆序数   戳这里   C题模板（归并排序求逆序数）  #include <bits/stdc++.h> using namespace std; typedef long long LL; vector<int> v; LL merge_sort( vector<int> &v ) { int n = v.size(); if( n <= 1 ) return 0; LL cnt = 0; vector&...

题目训练网址（密码hpuacm）：https://vjudge.net/contest/243680   先说一下归并排序求逆序数法 什么事逆序数   戳这里   C题模板（归并排序求逆序数）  #include <bits/stdc++.h> using namespace std; typedef long long LL; vector<int> v; LL merge_sort( vector<int> &v ) { int n = v.size(); if( n <= 1 ) return 0; LL cnt = 0; vector&...

训练题目网址（密码hpuacm2017）： https://vjudge.net/contest/244053    记好下面的模板  #include <bits/stdc++.h> using namespace std; const int MAXN = 1000+10; int ma[MAXN][MAXN]; int vis[MAXN]; int n, m; void topo_sort() { for( int i=1; i<=n; i++ ) // 因为有n个顶点一定要循环n次 { for( int j=1; j<=n; j++ ) // 每次从头开始找入度...

训练题目网址（密码hpuacm2017）： https://vjudge.net/contest/244053    记好下面的模板  #include <bits/stdc++.h> using namespace std; const int MAXN = 1000+10; int ma[MAXN][MAXN]; int vis[MAXN]; int n, m; void topo_sort() { for( int i=1; i<=n; i++ ) // 因为有n个顶点一定要循环n次 { for( int j=1; j<=n; j++ ) // 每次从头开始找入度...

题目链接（密码hpuacm）：https://vjudge.net/contest/243307 八成都是水题。 A题猴子吃桃太水。 B题疯狂的母牛，分别用三个变量保存一年，二年和三年龄的牛。第四年时三年龄的牛就要生小牛了。 注意一点就是，第一年只有一头三年龄的母牛。 C题 2的n-k次方 D题 贪心，把线段按照起点的从小到大排序，起点一样按终点小的排在前面。然后循环一边，每次取相邻两个线段的重叠长度，和与之前已经得到的重叠长度的最大值。  #include <stdio.h> #include<iostream> #include<algorithm> u...