概念如下：
狄尔沃斯定理_百度百科 (baidu.com)
本质就是找要求序列中最长的单调的子序列（不一定连续）的长度。
模板如下：
时间复杂度为O（N^2）
#include<iostream>
using namespace std;
int dp[100005],a[100005],n,maxx=-999;
//dp[i]记录以i结尾的最长上升子序列
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],dp[i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);
}
maxx=max(maxx,dp[i]);
}
cout<<maxx;
return 0;
}代码优化：
举个例子：
现在有序列4，8，9，5，6，7，2，7求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;
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];
}题目如下：
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 = 1; i <= n; i++) cin >> a[i],dp[i] = 1; //初始化
int cnt = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < i; j++)
{
if (a[i] <= a[j]) dp[i] = max(dp[i], dp[j] + 1);
}
cnt = max(cnt, dp[i]);
}
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];
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;
}
2、木棍加工
思路：
1、先对宽度进行排序，然后对宽度相同的进行长度排序；大的在前，小的在后
2、然后对已经排好的数组，统计最长连续单调递减子序列数目即可。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
int f[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;
f[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) f[i] = max(f[i], f[j] + 1);
}
cnt = max(cnt, f[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;
}
