wordpress简单易懂的网站,甘肃张掖网站建设,自动生成logo的网站,360收录入口动态规划分为很多模型#xff0c;比如说数字三角形模型#xff0c;最长上升子序列模型#xff0c;背包模型#xff0c;状态机模型#xff0c;状态压缩#xff0c;区间dp#xff0c;树形dp等等 下面#xff0c;我就Acwing提高课中#xff0c;最长上升子序列模型进行了整…动态规划分为很多模型比如说数字三角形模型最长上升子序列模型背包模型状态机模型状态压缩区间dp树形dp等等 下面我就Acwing提高课中最长上升子序列模型进行了整理。
涉及知识点总览
主要涉及的算法知识点有:
最长上升子序列 O(N2)O(N^2)O(N2)和O(NlogN)O(NlogN)O(NlogN)求解方法正反双向 LIS最大上升子序列和偏序集-Dilworth定理的两种证明
这里补充一个 O(N2)O(N^2)O(N2) dp 数组的优化 f[i] 代表的是 以 i 为结尾的最长上升子序列的长度他需要 f[i-1] …f[i-2] … 的信息来更新自己 参考网上思路发现可以用树状数组。用数值做下标维护长度最大值从后往前循环每次查询之前已经放到树状数组里面的数中以这个数结尾的最长不上升子序列的长度的最大值然后把这个最大值1作为以自己结尾的最长不上升子序列的长度放到树状数组里面
这里我们简单温习一下树状数组:
一、怪盗基德的滑翔翼
题目链接如下 怪盗基德的滑翔翼 根据题目的描述信息可知该题目就是要求对于某一个建筑往 左 能够最长下降子序列的长度或者是往 右的租场下降子序列的长度因此有两种解法一种是我们常见的dp最长上升子序列还有一种就是贪心最长上升子序列。 下面是我给出的两种解法具体的解释都放在了代码里面
#include bits/stdc.h
using namespace std;const int N 110;
int f[N], a[N], g[N];
int ans, n;/*dp LISf[i] f[j] 1 (j i a[j] a[i])正方跑两次
*/
void sol1() {int ans 0;for (int i 1; i n; i ) {f[i] 1;for (int j 1; j i; j ) {if (a[j] a[i]) {f[i] max(f[i], f[j] 1);}}ans max(ans, f[i]);}for (int i n; i 1; i -- ) {g[i] 1;for (int j n; j i; j -- ) {if (a[j] a[i]) {g[i] max(g[i], g[j] 1);}}ans max(ans, g[i]);}printf(%d\n, ans);
}/*使用最长上升子序列模型的贪心解法f[i] 表示长度为 i 的最小末尾不难得知f[i] 数组应该是单调递增的(相等的情况都不会出现)对于每次循环 数组 a 的元素都是将 寻找小于 a[i] 的最大 f[j] 的位置然后更新f[j 1]初始化数组memset(f, 0x3f, sizeof f), f[0] 0;
*/
void sol2() {int len 1, ans 0;memset(f, 0x3f, sizeof f);f[0] 0;f[1] a[1];for (int i 2; i n; i ) {static int l, r, mid;l 0, r len;while (l r) {mid l r 1 1; // 注意这里的 1if (f[mid] a[i]) {l mid;} else {r mid - 1;}}f[l 1] a[i];len max(len, l 1); // 更新 len}ans max(ans, len);len 1;memset(f, 0x3f, sizeof f);f[0] 0;f[1] a[n];for (int i n - 1; i 1; i -- ) {static int l, r, mid;l 0, r len;while (l r) {mid l r 1 1; // 注意这里的 1if (f[mid] a[i]) {l mid;} else {r mid - 1;}}f[l 1] a[i];len max(len, l 1);}ans max(ans, len);printf(%d\n, ans);
}int main()
{int T; cin T;while (T -- ) {scanf(%d, n);for (int i 1; i n; i ) {scanf(%d, a[i]);}// sol1();sol2();}return 0;
}二、登山
Acwing 登山题目链接 该登山题目和原本的 怪盗基德 问题有些类似但是又有些不同他们都需要正反两次求出最长上升子序列但是不同的是怪盗基德可以使用 nlog(n) 的贪心算法因为他不必在意于最后的结尾是哪个点。 但是登山问题是需要知道 该点的位置是在哪里的。 因此登山问题必须要使用 O(N2)O(N^2)O(N2)的dp求解 f[i] 表示以i 为结尾的最长上升子序列
#include bits/stdc.h
using namespace std;const int N 1010;
int f[N], a[N], g[N];
int ans, n;/*dp LISf[i] f[j] 1 (j i a[j] a[i])正方跑两次
*/
void sol1() {int ans 0;for (int i 1; i n; i ) {f[i] 1;for (int j 1; j i; j ) {if (a[j] a[i]) {f[i] max(f[i], f[j] 1);}}}for (int i n; i 1; i -- ) {g[i] 1;for (int j n; j i; j -- ) {if (a[j] a[i]) {g[i] max(g[i], g[j] 1);}}}for (int i 1; i n; i ) {ans max(ans, f[i] g[i] - 1); // 注意这里的 - 1}printf(%d\n, ans);
}int main()
{int T; T 1;while (T -- ) {scanf(%d, n);for (int i 1; i n; i ) {scanf(%d, a[i]);}sol1();}return 0;
}三、合唱队形 Acwing 合唱队型 本题就是换了一种问法最少有多少同学出列就是需要求出我们的最长上升子序列和我们的登山问题是一个性质也是只可以使用O(N2)O(N^2)O(N2)算法进行求解
#include bits/stdc.h
using namespace std;const int N 1010;
int f[N], a[N], g[N];
int ans, n;/*dp LISf[i] f[j] 1 (j i a[j] a[i])正方跑两次
*/
void sol1() {int ans 0;for (int i 1; i n; i ) {f[i] 1;for (int j 1; j i; j ) {if (a[j] a[i]) {f[i] max(f[i], f[j] 1);}}}for (int i n; i 1; i -- ) {g[i] 1;for (int j n; j i; j -- ) {if (a[j] a[i]) {g[i] max(g[i], g[j] 1);}}}for (int i 1; i n; i ) {ans max(ans, f[i] g[i] - 1); // 注意这里的 - 1}printf(%d\n, n - ans);
}int main()
{int T; T 1;while (T -- ) {scanf(%d, n);for (int i 1; i n; i ) {scanf(%d, a[i]);}sol1();}return 0;
}四、友好城市
Acwing 友好城市链接 对于本题而言他所求的不相交的航线就是我们排序之后的不递减子序列 排序可以按照是左岸排序也可以按照右岸进行排序
/*
这个题目个关键在于你连一连这个友好城市的航线你就会发现
航线不相交就是排序之后他们的那个最长上升子序列
*/
#include bits/stdc.h
using namespace std;
const int N 5010;
int n, f[N], len;class Node {
public:int x, y;Node() {//}Node(int x, int y): x(x), y(y) {//}}a[N];
bool cmp1(const Node t1, const Node t2) {if (t1.x t2.x) {return t1.y t2.y;} else {return t1.x t2.x;}
}
bool cmp2(const Node t1, const Node t2) {if (t1.y t2.y) {return t1.x t2.x;} else {return t1.y t2.y;}
}int sol1() {sort(a 1, a n 1, cmp1);// sort(a 1, a n 1, cmp2);// 求解的是最长非递减子序列/*因此变成了寻找 f[i] 中 小于等于 val 的最大位置*/int val;memset(f, 0x3f, sizeof f);f[0] 0;len 0;for (int i 1; i n; i ) {val a[i].y;static int l, r, mid;l 0, r len;while (l r) {mid l r 1 1;if (f[mid] val) { // 注意这里是 小于等于l mid;} else {r mid - 1;}}f[l 1] val;len max(len, l 1);}cout len endl;
}int sol2() {sort(a 1, a n 1, cmp2);// 求解的是最长非递减子序列/*因此变成了寻找 f[i] 中 小于等于 val 的最大位置*/int val;memset(f, 0x3f, sizeof f);f[0] 0;len 0;for (int i 1; i n; i ) {val a[i].x;static int l, r, mid;l 0, r len;while (l r) {mid l r 1 1;if (f[mid] val) { // 注意这里是 小于等于l mid;} else {r mid - 1;}}f[l 1] val;len max(len, l 1);}cout len endl;
}int main()
{cin n;for (int i 1; i n; i ) {scanf(%d%d, a[i].x, a[i].y); }//sol1();sol2();return 0;
}五、最大上升子序列和
Acwing 最大上升子序列和链接 原本的最长上升子序列有两种求解方法一个是 dp 求解一个是类似于折半查找的贪心求解 本题的最大上升子序列和能否也用这两种方法呢 dp求解是显然可以使用的贪心求解的话我们尽心探讨
LIS可以使用贪心求解是因为 f[i] 数组代表 长度 为 i 的最小末尾然后利用该数组的单调特性进行优化Nlog(N)Nlog(N)Nlog(N) 但是此时的 f[i] 数组倘若代表的是 和为 i, 的最小末尾首先存不下而且也没有单调性可言(主要是因为 len是连续的但是和不是连续的len是有0,1,2, 3, 4, 5但是和的话是跳跃性的没办法)所以无法进行类似的优化还是得 O(N2)O(N^2)O(N2)的算法
#include bits/stdc.h
using namespace std;const int N 1010;
int n, f[N];
int a[N];int main()
{cin n;for (int i 1; i n; i ) {scanf(%d, a[i]);}memset(f, 0, sizeof f);int ans 0;for (int i 1; i n; i ) {f[i] a[i];for (int j 1; j i; j ) {if (a[j] a[i]) {f[i] max(f[i], f[j] a[i]);}}ans max(ans, f[i]);}cout ans endl;return 0;
}六、拦截导弹
Acwing 拦截导弹链接
首先 不难得知一套系统最多拦截的导弹数目 那么就是最长非递增子序列
最少使用多少套系统最少有多少个 非递增子序列 他的个数就等于 递增子序列的个数(这是一个定理)
拦截所有导弹最少要配备的系统数 使用贪心的算法进行证明 使用一个队列过来一个导弹 1.1 可以加入队列后面那么就加入最小的后面(队列是 有序的也就是二分查找大于等于 x 的最小数值将他放在后面) 1.2 不可以加入队列后面新开一个 你发现这个过程是完完全全和最上升子序列一样 下面我给出最长上升子序列的算法过程: f[i] 表示长度为 i 的上升子序列的最小末尾对于每个加入的 val我们进行一下的操作 1.1 二分查找 f 数组中小于 val 的最大数值 f[j]然后将 val 放至 f[j 1] 中这一步可以看做是二分查找 f 数组中 大于等于 val 的最小数值 f[j] 将 val 更新 f[j] 完全吻合
通过贪心该算法得以证明 使用偏序集中的Dilworth 定理进行证明 首先我们先介绍一下概念(参考百度百科) 偏序集合英语Partially ordered set简写 poset在数学中特别是序理论中是指配备了偏序关系的集合。这个关系形式化了排序、顺序或排列这个集合的元素的直觉概念。这种排序不必然需要是全部的就是说不需要但也可以保证在这个集合内的所有对象的相互可比较性。(在数学用法中全序是一种偏序)。偏序集合定义了偏序拓扑。 设R是非空集合A上的一个二元关系若R满足 自反性、反对称性、传递性则称R为A上的偏序关系。 非严格偏序自反偏序 给定集合S“≤”是S上的二元关系若“≤”满足 1 自反性∀a∈S有a≤a 2 反对称性∀ab∈Sa≤b且b≤a则ab 3 传递性∀abc∈Sa≤b且b≤c则a≤c 则称“≤”是S上的非严格偏序或自反偏序。 严格偏序反自反偏序 给定集合S“”是S上的二元关系若“”满足 1 反自反性∀a∈S有a≮a 2 非对称性∀ab∈Sab ⇒ b≮a 3 传递性∀abc∈Sab且bc则ac 则称“”是S上的严格偏序或反自反偏序。 严格偏序与有向无环图(dag)有直接的对应关系。一个集合上的严格偏序的关系图就是一个有向无环图。其传递闭包是它自己。 极小元、链、反链定义 在X中对于元素a如果任意元素b由b≤a得出ba则称a为极小元。 一个反链A是X的一个子集它的任意两个元素都不能进行比较。 一个链C是X的一个子集它的任意两个元素都可比。 Dilworth 定理 对于一个偏序集其最少链划分数等于其最长反链的长度。 Dilworth 定理是如何证明的呢 该定理也可以理解为对于一个偏序集他的最长链的长度 等于 其最少反链划分数
首先我们假设他的最长链的长度为 xxx最少反链划分数为 yyy因为最长链中的元素并不满足反偏序的性质因此最少反链划分数量 yyy 应该大于等于 最长链的数量 xxx即 y≥xy\geq xy≥x设X1XA1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2必存在X1中的元素a1使得a1a2。令A2是X2中极小元的集合从X2中删除A2得到X3……最终会有一个Xk非空而X(k1)为空。于是A1,A2,…,Ak就是X的反链的划分同时存在链a1a2…ak其中ai在Ai内。由于xxx是最长链大小因此xxxk。由于X被划分成了k个反链因此x≥k≥yx\geq k\geq yx≥k≥y。因此xyxyxy定理1得证。
参考链接
因此可以 O(NlogN)O(NlogN)O(NlogN)解决代码对应如下
/*
问题一一套系统最多可以拦截多少导弹 最长不上升子序列问题二拦截所有导弹最少要配备的系统数是用贪心的算法使用一个队列过来一个导弹1. 可以加入队列后面那么就加入最小的后面2. 不可以加入队列后面新开一个你发现这个过程是完完全全和最长上升子序列算法过程一样
*/
#include bits/stdc.h
using namespace std;const int INF 0x3f3f3f3f;
const int N 10010;
int a[N], f[N], len, n;int main()
{ string s;getline(cin, s);stringstream ss(s);n 0;while (ss a[ n]);n --;/*for (int i 1; i n; i )printf(%d, , a[i]);puts();*/// 最长非递增子序列/*f[i] 应该是长度为 n 结尾的最大值每次应该是需要找 大于等于 x 的最小值*/memset(f, 0, sizeof f);f[0] INF;len 0;for (int i 1; i n; i ) {static int l, r, mid, val;l 0, r len, val a[i];while (l r) {mid l r 1 1;if (f[mid] val) {l mid;} else {r mid - 1;}}f[l 1] val;len max(len, l 1);}cout len endl;// 最长上升子序列memset(f, 0x3f, sizeof f);f[0] 0;len 0;for (int i 1; i n; i ) {static int l, r, mid, val;l 0, r len, val a[i];while (l r) {mid l r 1 1;if (f[mid] val) {l mid;} else {r mid - 1;}}f[l 1] val;len max(len, l 1);}cout len endl;return 0;
}
