例题3.4查找（哈工大复试）链接 关键字：二分查找、排序 二分查找要点： 1. 系统自带lower_bound(nums.begin(), nums.end(), targetNumber) - nums.begin();返回的>=目标值的第一个位置（可能返回的是那个大于目标值的位置，有可能序列中没有>=该数的则返回n） 2. 自写的二分查找 方法一：C++自带二分查找 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() {...

例题12.7 点菜问题（北京大学复试）链接 关键字：0-1背包、动态规划 算法：设计dp[i][j] 用来存储将物品i放入背包中后可以达到的最大的价值j 分两种情况： CASE1: 当前背包没有足够空间，无法将商品 i 放入其中，此时的转移方程即为dp[i][j] = dp[i-1][j] CASE2: 当前背包的空间充足，可以放入当前的商品i，这时候需要考虑两种情况，即将商品i放入其中取得的最大价值和不将商品i放入取得的最大价值中最大的那一个，此时转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]) #inclu...

Coincidence(找到两个字符串的最长公共子串)（上海交通大学） 关键字：动态规划、最长公共字 关键需要处理好边界点，不然计算比较麻烦 ">#include<vector> #include<string> using namespace std; //P236 习题12.4 int main() { //1. input data string str1, str2; cin >> str1 >> str2; int m = str1.size(); int n = str2.size(); //2.compute dp[i][j] ve...

习题12.3合唱队形(北京大学复试题) 合唱队列是升级版的 最大上升子序列问题 + 动态规划法 考虑节点i，节点i左边需要的是最大上升子序列，节点右边是最大下降子序列问题，分别用dp1[i]和dp2[i]来存储 max(dp1[i] + dp2[i] -1) 即为最大的符合条件的队列的人数，用总人数n - (dp1[i] + dp2[i] -1) 即为所求 ">#include<vector> using namespace std; int main() { int n; cin >> n; vector<int> nums(n); //1. input ...

12.4拦截导弹（北京大学复试） 问题分类：动态规划法 + 最长递增子序列问题 dp[i]取值的两种可能  nums[i]之前的元素都比i大，即最长的递归子序列只有nums[i]本身，那么dp[i] = 1 nums[i]之前存在numsj比nums[i]大，那么dp[i] = dp[j]+1;  状态转移方程为： dp[i] = max(1, dp[j] +1) 其中 j为 满足(j<i && nums[j] > nums[i])的全部的j 因为有很多个j，循环时应写成，dp[i] = 1, dp[i] = max(dp[i], dp[j] +1); ans = ...

最大连续子序列（浙江大学复试题） 动态规划问题 在最大连续子序列的基础问题上，要求输出子序列的第一个和最后一个数据，且对子序列全部为负数时需进行单独的处理 ">#include<vector> using namespace std; int main() { int n; while (cin >> n) { if (n == 0) return 0; vector<int> nums(n), dp(n); //1. input data bool ifAllMinus = true; for (int i = 0; i < n; i++) { ci...

12.3最大子矩阵（北京大学复试题） 王道课本P227 例12.3 本题是最大连续子序列的变种问题，需要将矩阵压缩成一维问题，当作最大连续子序列和问题来处理，再利用动态规划法问题求解dp[n] CASE 1: i == j (矩阵matrix的i行和j行为同一行时，就是最大连续子序列问题) CASE 2: i != j 时，可以将矩阵i行到j行压缩成一行，然后转换成一维的最大连续子序列问题来处理 #include<iostream> #include <vector> using namespace std; //例12.3最大子矩阵 const int inf = I...

N阶楼梯上楼问题 本题为经典的动态规划问题 动态规划相比于暴力的递归解法的区别在于动态规划法合理利用已经求解过的子问题用来求解最终的问题 动态规划的关键点在：  记忆数组：dp用来记忆每次求解的子问题 递推公式：dp[n] = dp[n-1] + dp[n-2]; 初始条件：dp[1]第一阶台阶的登上方法只有一种，dp[2]第二阶台阶的登上方法有两种，以此初始条件进行递推即可  #include <vector> using namespace std; int main() { vector<int> dp(90); int n; while (cin >&gt...

15号面试，18号笔试，20号补充了材料，快一周了，没有一点消息。。。稍微有点慌。。。有没有开奖的？