本文共 10797 字,大约阅读时间需要 35 分钟。
动态规划分为很多模型,比如说数字三角形模型,最长上升子序列模型,背包模型,状态机模型,状态压缩,区间dp,树形dp等等
下面,我就Acwing提高课中,最长上升子序列模型进行了整理。主要涉及的算法知识点有:
这里补充一个 O ( N 2 ) O(N^2) O(N2) dp 数组的优化
f[i] 代表的是 以 i 为结尾的最长上升子序列的长度,他需要 f[i-1] …f[i-2] … 的信息来更新自己 参考网上思路,发现可以用树状数组。用数值做下标,维护长度最大值,从后往前循环,每次查询之前已经放到树状数组里面的数中以这个数结尾的最长不上升子序列的长度的最大值,然后把这个最大值+1作为以自己结尾的最长不上升子序列的长度,放到树状数组里面这里我们简单温习一下树状数组:
题目链接如下
#includeusing namespace std;const int N = 110;int f[N], a[N], g[N];int ans, n;/* dp LIS f[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; // 注意这里的 + 1 if (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; // 注意这里的 + 1 if (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;}
#includeusing namespace std;const int N = 1010;int f[N], a[N], g[N];int ans, n;/* dp LIS f[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;}
#includeusing namespace std;const int N = 1010;int f[N], a[N], g[N];int ans, n;/* dp LIS f[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;}
/*这个题目个关键在于,你连一连这个友好城市的航线,你就会发现航线不相交,就是排序之后他们的那个最长上升子序列*/#includeusing 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;}
LIS可以使用贪心求解,是因为 f[i] 数组代表 长度 为 i 的最小末尾,然后利用该数组的单调特性,进行优化, N l o g ( N ) Nlog(N) Nlog(N)
但是,此时的 f[i] 数组倘若代表的是 和为 i, 的最小末尾,首先存不下,而且也没有单调性可言(主要是因为 len是连续的,但是和不是连续的,len是有0,1,2, 3, 4, 5,但是和的话是跳跃性的没办法),所以无法进行类似的优化,还是得 O ( N 2 ) O(N^2) O(N2)的算法#includeusing 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;}
首先 不难得知,一套系统最多拦截的导弹数目 那么就是最长非递增子序列
最少使用多少套系统,最少有多少个 非递增子序列
他的个数就等于 递增子序列的个数(这是一个定理)拦截所有导弹最少要配备的系统数:
使用贪心的算法进行证明使用一个队列,过来一个导弹
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 反对称性:∀a,b∈S,a≤b且b≤a,则a=b; 3 传递性:∀a,b,c∈S,a≤b且b≤c,则a≤c; 则称“≤”是S上的非严格偏序或自反偏序。
严格偏序,反自反偏序
给定集合S,“<”是S上的二元关系,若“<”满足: 1 反自反性:∀a∈S,有a≮a; 2 非对称性:∀a,b∈S,a<b ⇒ b≮a; 3 传递性:∀a,b,c∈S,a<b且b<c,则a<c; 则称“<”是S上的严格偏序或反自反偏序。 严格偏序与有向无环图(dag)有直接的对应关系。一个集合上的严格偏序的关系图就是一个有向无环图。其传递闭包是它自己。
极小元、链、反链定义
在X中,对于元素a,如果任意元素b,由b≤a得出b=a,则称a为极小元。 一个反链A是X的一个子集,它的任意两个元素都不能进行比较。 一个链C是X的一个子集,它的任意两个元素都可比。
Dilworth 定理
对于一个偏序集,其最少链划分数等于其最长反链的长度。
Dilworth 定理是如何证明的呢?
该定理也可以理解为,对于一个偏序集,他的最长链的长度 等于 其最少反链划分数因此可以 O ( N l o g N ) O(NlogN) O(NlogN)解决,代码对应如下
/*问题一: 一套系统,最多可以拦截多少导弹, 最长不上升子序列问题二: 拦截所有导弹最少要配备的系统数: 是用贪心的算法 使用一个队列,过来一个导弹 1. 可以加入队列后面,那么就加入最小的后面 2. 不可以加入队列后面,新开一个 你发现这个过程是完完全全和最长上升子序列算法过程一样*/#includeusing 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;}
转载地址:http://suxpz.baihongyu.com/