U4

学习目标 贪心算法 [导弹拦截] 【算法分析】 首先考虑第一问，即序列中的最长不上升子序列。 令 g 为以 i 结尾的最长不上升子序列的值，那么可以枚举 g 1 ​ ~ gi−1，若 a j ​ ≤a i ​ ，则 g i ​ =max(g i ​ ,g j+1 ​ )，否则 g i ​ =max( ......

学习目标 前缀和解决的问题 前缀和概念 前缀和构建方式 前缀和主要解决区间求和问题 练习题1：[前缀和] 【算法分析】 前缀和数组 s 的含义是 s[i] 表示 a[1] ~ a[i] 的和 ，那么 ∑ i=l i=r ​ a[i] = s[r]−s[l−1]。 【参考代码】 #include <i ......

import json # 把包含\\u4f20\\u5a92 unicode内容的字典字符串变成字典 def text_to_dict(text): dict1 = json.loads(text) str_dict = str(dict1).replace('\\xa0','').replace ......

学习目标 STL 栈stack [入栈出栈] 【算法分析】 栈的基本操作。 【参考代码】 #include <bits/stdc++.h> using namespace std; int main() { stack<int>st; int n; cin >> n; for (int i = 1; ......

队列：顺序队列 队列基本操作 选择题1 选择题2 程序阅读题 打疫苗 【算法分析】 用数组实现队列，按题意模拟即可。 【参考代码】 #include <iostream> using namespace std; string q[1010]; int f, r; //f前端，指向队头，r后端，指向 ......

上节课作业讲解视频： 链接：https://pan.baidu.com/s/1JLX8ZIGJFzoRtGASZIINsw?pwd=qzwj提取码：qzwj 学习目标 栈 按顺序进栈 出栈 练习 练习： 练习 练习2 程序阅读题练习 [模拟栈操作] 【算法分析】 定义数组 s 模拟栈，TOP 为指向 ......

上节课作业解析 链接：https://pan.baidu.com/s/1QCDg1GXb5HhrpkPgomOCyg?pwd=s4b4 提取码：s4b4 二分答案学习目标 二分查找单调性意思 二分答案单调性 二分答案的思路 [【二分答案】砍树(简单版)] 枚举每一棵树，注意当锯片高度高于树的高度时砍 ......

上节课作业部分(点击跳转) 引入 分治算法概念 二分法分治思想 编程题 二分查找能解决的问题不仅仅是找到一个值 题1： 要在一个有序序列中查找一个数，可以使用二分算法。 include <iostream> using namespace std; int BinarySearch(int a[], ......

上节课作业部分(点击跳转) 排列组合 排列 组合： 练习题目 题2 编程题1，用递推求组合数 编程题3： [【递推】直线分割平面问题] 【算法分析】 用 a[i] 表示 i 条直线最多能将这个圆分割成的部分数: 当 i=1 时，a[1]=2; 当 i=2 时，a[2]=4; 当 i=3 时，a[3] ......

上节课作业部分(点击跳转) 加法原理和乘法原理 递推的概念 练习题1、[兔子数列] 【算法分析】 初始条件：第 1 个月有 1 对兔子，第 2 个月有 1 对兔子。 当大于等于 3 个月时：第 i 个月兔子数 = 第 i−1 个月兔子数+第 i−2 个月兔子数。 【参考代码】 include <io ......

上节课作业部分 [纪念品分组] 【算法分析】 贪心算法：先对数组从小到大排序，用 l=1, r=n 指针指向首尾元素；如果 pl+pr≤w，则将pl和pr分一组，指针 l++,r--。如果 pl+pr>w，则将 pr单独作为一组，指针 r--。如此反复直到取完所有元素。 #include <iost ......

本节学习目标：贪心算法的概念以及对应练习题 贪心算法概念 贪心算法的特点 利用贪心算法的两个性质 练习1：最优装载问题 【本题算法分析】 优先把重量小的物品放进去，在容量固定的情况下，装的物品量最多。因此采用重量最轻者先装的贪心选择策略，可从局部最优达到全局最优。 参考代码 #include <io ......