Dilworth定理：最少的下降序列个数就等于整个序列最长上升子序列的长度
Dilworth定理：最少的下降序列个数就等于整个序列最长上升子序列的长度
概念如下：
本质就是找要求序列中最长的单调的子序列（不一定连续）的长度。
最长上升子序列（Longest Increasing Subsequence），简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数
假设我们有一个序列 b i，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们也可以从中得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N，但必须按照从前到后的顺序。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，我们就会得到一些上升的子序列，如(1, 7, 9), (3, 4, 8), (1, 3, 5, 8)等等，而这些子序列中最长的（如子序列(1, 3, 5, 8) ），它的长度为4，因此该序列的最长上升子序列长度为4。
下面是最长单调递增子序列长度
模板如下：
时间复杂度为O（N^2）
#include <iostream>
#include <algorithm>
using namespace std;
int a[5005], dp[5005];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i], dp[i] = 0; //初始化
int cnt = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (a[i] <= a[j]) dp[i] = max(dp[i], dp[j] + 1);
}
cnt = max(cnt, dp[i]);
}
cout<<cnt<<endl;
return 0;
}代码优化：
举个例子：
现在有序列4，8，9，5，6，7，2，7求 最长上升子序列（Longest Increasing Subsequence）简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。
一个一个元素来看，首先无疑dp[1]=4 ，然后考察8，8>4，故把8加入尾部。然后9>8，也进入尾部，这时dp数组是{4, 8, 9}。
下一个元素是5，5<9，不能塞入尾部。我们找到第一个大于等于5的元素，是8。4->8是长度为2的上升子序列，4->5也是，但是5比8更小，所以更有潜力更新后面的子序列。所以把8换成5，现在DP是{4, 5, 9}。同样的道理DP又变成{4, 5, 6}。
现在我们尝到甜头了，因为下一个元素是7，本来是没有机会进入序列的，现在却可以了。于是dp变成{4, 5, 6, 7}。注意，显然DP是递增的（两种转移都不会破坏递增性），但这并不意味着它就是所求的上升子序列，你看，下一个元素是2，它会把dp更新成{2, 5, 6, 7}，但原序列并没有一个子序列是{2, 5, 6, 7}。
最后剩一个元素7，由于我们在求严格上升的子序列，不能将它插入尾部，于是我们把7替换成7——这个元素对子序列长度没有贡献。好了，最后得到的数组长度是4，所以最长上升子序列的长度就是4 。
刚刚提到，dp是递增的，所以我们不用每次都扫描一遍数组， 而可以进行二分查找。这样，就把复杂度降到了 𝑂(𝑛log𝑛) ，具体地，代码如下
int len = 0;
memset(dp, 127, sizeof(dp));
for (int i = 0; i < n; i++)
{
if (dp[len] >= a[i]) dp[++len] = a[i];//若a[i]>=dp[ans]，直接把a[i]接到后面
//else *upper_bound(dp + 1, dp + len + 1, a[i], greater<int>()) = a[i]; //找到第一个大于a[i]的数字
//上下等价
else
{
int l = 0, r = len;
while (l < r)
{
int mid = l + r >> 1;
if (dp[mid] < a[i]) r = mid;
else l = mid + 1;
}
dp[l] = a[i];
}
}题目如下：
1、我最喜欢吃饭了
把n个人提出来成为原序列的一个子序列，根据题意这个子序列中的元素是单调递增的（即后一项总是大于前一项），我们称为单调递增子序列。本问所求n个人顺序最多需要需要多少个窗口，即求最长的单调递增子序列数目。
#include <iostream>
#include <algorithm>
using namespace std;
int a[5005], dp[5005];
int main()
{
int n, m;
cin >> n >> m;// n个人m个窗口
for (int i = 0; i < n; i++) cin >> a[i], dp[i] = 1; //初始化
int cnt = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (a[i] <= a[j]) dp[i] = max(dp[i], dp[j] + 1);
}
cnt = max(cnt, dp[i]);
}
cout<<cnt<<endl;
if (cnt >= m)cout << "Karashi lovelove" << endl;//非法
else cout << "Karashi cblcd" << endl;//合法
return 0;
}代码优化
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[5005], dp[5005];
int main()
{
int n, m;
cin >> n >> m;// n个人m个窗口
for (int i = 0; i < n; i++) cin >> a[i];
int len = 0;
memset(dp, 127, sizeof(dp));
for (int i = 0; i < n; i++)
{
if (dp[len] >= a[i]) dp[++len] = a[i];//若a[i]>=dp[ans]，直接把a[i]接到后面
else *upper_bound(dp + 1, dp + len + 1, a[i], greater<int>()) = a[i];
}
//cout << len << endl;
if (len > m)cout << "Karashi lovelove" << endl;//非法
else cout << "Karashi cblcd" << endl;//合法
return 0;
}代码详细：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[5005], dp[5005];
int main()
{
int n, m;
cin >> n >> m;// n个人m个窗口
for (int i = 0; i < n; i++) cin >> a[i];
int len = 0;
memset(dp, 127, sizeof(dp));
for (int i = 0; i < n; i++)
{
if (dp[len] >= a[i]) dp[++len] = a[i];//若a[i]>=dp[ans]，直接把a[i]接到后面
//else *upper_bound(dp + 1, dp + len + 1, a[i], greater<int>()) = a[i]; //找到第一个大于a[i]的数字
//上下等价
else
{
int l = 0, r = len;
while (l < r)
{
int mid = l + r >> 1;
if (dp[mid] < a[i]) r = mid;
else l = mid + 1;
}
dp[l] = a[i];
}
}
//cout << len << endl;
if (len > m)cout << "Karashi lovelove" << endl;//非法
else cout << "Karashi cblcd" << endl;//合法
return 0;
}2、木棍加工
思路： 1、先对宽度进行排序，然后对宽度相同的进行长度排序；大的在前，小的在后 2、然后对已经排好的数组，统计最长连续单调递减子序列数目即可。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
int dp[N];
struct Data
{
int l, w;
}a[N];
bool cmp(Data a,Data b) //先排序宽度，再排序长度
{
if (a.w != b.w) return a.w > b.w;
return a.l > b.l;
}
int main()
{
int n;
cin >> n ;
for (int i = 1; i <= n; i++)
{
cin >> a[i].l >> a[i].w;
dp[i] = 1; //初始化
}
int cnt = 1;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) //后者与前者比长度
{
for (int j = 1; j < i; j++)
{
if (a[i].l > a[j].l) dp[i] = max(dp[i], dp[j] + 1);
}
cnt = max(cnt, dp[i]);
}
cout << cnt << endl;
return 0;
}3、导弹拦截
典型上述题型，但是下面会超时，因此我们要用到二分查找
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
int dp1[N],a[N],dp2[N];
int main()
{
int n = 0;
while (cin >> a[n])
{
n++;
}
int mx1 = 0, mx2 = 0;
for (int i = 0; i < n; i++)
{
dp1[i] = 1, dp2[i] = 1;
for (int j = 0; j < i; j++)
{
if (a[j] < a[i]) dp1[i] = max(dp1[i], dp1[j] + 1);
if (a[j] >= a[i]) dp2[i] = max(dp2[i], dp2[j] + 1);
}
mx1 = max(mx1, dp1[i]); //最长单调连续递增子序列
mx2 = max(mx2, dp2[i]); //最长单调连续递减子序列
}
cout << mx2 << endl;
cout << mx1 << endl;
return 0;
}代码优化 变量声明： 数组 a 存储从输入数据； 数组 dp 存储最长不上升子序列； 变量 len 代表 dp 的结尾位置（即最长不上升子序列的长度）。
把 a 中的每个元素挨个放到 dp 里：
- 如果 a[i] ≤ dp[len]，说明 ai 可以直接加入 dp（而整个 dp 数组还是有序的）；
- 如果 a[i] > dp[len]，说明若放入 a[i] 则 dp 会无序，所以要找办法把 a[i] 放进去：
怎么放呢？在 dp 中找到第一个小于 a[i] 的数，用 a [i] 代替它。
找到第一个小于 a[i] 的数，使用 upper_bound 可以在 O(logn) 复杂度内找到（需要改比较器）。
由于它返回的是指针就可以有一些奇特操作。
*upper_bound(dp + 1, dp + len + 1, A[i], greater<int>()) = A[i]; *lower_bound(dp + 1, dp + len + 1, a[i]) = a[i];
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int dp[N],a[N];
int main()
{
int n = 0, len = 0;
while (cin >> a[n])
{
n++;
}
memset(dp, 127, sizeof(dp));
for (int i = 0; i < n; i++)
{
if (dp[len] >= a[i]) dp[++len] = a[i];
else *upper_bound(dp + 1, dp + len + 1, a[i], greater<int>()) = a[i];
}
cout << len << endl;
len = 0;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; ++i)
{
if (dp[len] < a[i])
dp[++len] = a[i];
else
*lower_bound(dp + 1, dp + len + 1, a[i]) = a[i];
}
cout << len << endl;
return 0;
}代码详细：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int b[N];
int a[N], f[N];
int res, cnt = 0, num = 0;
int main() {
while (scanf("%d", &b[++res]) != EOF) {
if (cnt == 0 || b[res] <= a[cnt]) a[++cnt] = b[res];
else {
int l = 1, r = cnt;
while (l < r) {
int mid = (l + r) >> 1;
if (a[mid] < b[res]) r = mid;
else l = mid + 1;
}
a[l] = b[res];
}
}
cout << cnt << endl;
num++, f[1] = b[1];
for (int i = 2; i <= res; i++) {
if (f[num] < b[i]) {
f[++num] = b[i];
//cout << b[i] << " " << f[num - 1] << endl;
continue;
}
int l = 1, r = num;
while (l < r) {
int mid = (l + r) >> 1;
if (f[mid] >= b[i]) r = mid;
else l = mid + 1;
}
f[l] = b[i];
}
cout << num << endl;
return 0;
}代码完整：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int dp[N], a[N];
int main()
{
int n = 0, len = 0;
while (cin >> a[n])
{
n++;
}
memset(dp, 127, sizeof(dp));
for (int i = 0; i < n; i++)
{
if (dp[len] >= a[i]) dp[++len] = a[i];
//找第一个大于的数
//else *upper_bound(dp + 1, dp + len + 1, a[i], greater<int>()) = a[i];
else //上下等价
{
int l = 0, r = len;
while (l < r)
{
int mid = l + r >> 1;
if (dp[mid] < a[i]) r = mid;
else l = mid + 1;
}
dp[l] = a[i];
}
}
cout << len << endl;
len = 0;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; ++i)
{
if (dp[len] < a[i]) dp[++len] = a[i];
//else*lower_bound(dp + 1, dp + len + 1, a[i]) = a[i];
else
{
int l = 0, r = len;
while (l < r)
{
int mid = l + r >> 1;
if (dp[mid] >= a[i]) r = mid;
else l = mid + 1;
}
dp[l] = a[i];
}
}
cout << len << endl;
return 0;
}4、Super Jumping! Jumping! Jumping!
玩家从起点出发，最终必须跳到终点。在跳跃过程中，玩家将访问路径上的棋子，但每个人都必须从一个棋子跳到另一个更大的棋子(你可以假设起点是最小值，终点是最大值)。所有玩家都不能倒退。一次跳跃可以从一个棋子跳到另一个棋子，也可以越过许多棋子，甚至你可以直接从起点到达终点。当然在这种情况下你得到0分。当且仅当玩家能够根据他的跳跃解决方案获得更大的分数时，他便是赢家。注意，你的得分来自于你跳跃路径上棋子的价值总和。
思路：用简单O(N^2)就可以过，暴力求解 用dp[i]来规划到该棋子时的最大价值
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[1005], dp[1005];
int main()
{
int n;
while ((cin >> n) && n)
{
memset(dp, 0,sizeof(dp));
for (int i = 0; i < n; i++) cin >> a[i];
dp[0] = a[0];
for (int i = 0; i < n; i++) //每走一步的最大值
{
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) dp[i] = max(a[i] + dp[j], dp[i]);
}
dp[i] = max(a[i], dp[i]);
}
int mx = 0;
for (int i = 0; i < n; i++) mx = max(dp[i], mx);
cout << mx << endl;
}
return 0;
}5、最长公共子序列
我们先来看看长度为n的序列a1和长度为m的序列a2最长公共子序列的匹配，暴力求解
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e3 + 10;;
int a1[N],a2[N], dp[N][N];
int main()
{
int n, m;
cin >> n >> m ;
for (int i = 1; i <= n; i++) cin >> a1[i];
for (int i = 1; i <= m; i++) cin >> a2[i];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (a1[i] == a2[j])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
cout << dp[n][n] << endl;
return 0;
}但是这个方法用在这个题目会超时
因此我们采用二分的方法对代码进行优化
因为两个序列都是n的全排列，那么两个序列元素互异且相同，也就是说只是位置不同罢了，那么我们通过一个map数组将A序列的数字在B序列中的位置表示出来——因为最长公共子序列是按位向后比对的，所以a序列每个元素在b序列中的位置如果递增，就说明b中的这个数在a中的这个数整体位置偏后，可以考虑纳入LCS——那么就可以转变成nlogn求用来记录新的位置的map数组中的**LIS**。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int a[N], b[N], map[N], dp[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], map[a[i]] = i;
for (int i = 1; i <= n; i++) cin >> b[i];
int len = 0;
memset(dp, 127, sizeof(dp));
dp[0] = 0;
for (int i = 1; i <= n; i++)
{
int l = 0, r = len;
if (map[b[i]] > dp[len]) dp[++len] = map[b[i]];
else
{
while (l < r)
{
int mid = (l + r) / 2;
if (dp[mid] > map[b[i]]) r = mid;
else l = mid + 1;
}
dp[l] = min(map[b[i]], dp[l]);
}
}
cout << len << endl;
return 0;
}腾讯云开发者
