题目描述
Dilwoth定理:
通俗解释: 把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度(LIS)。
最长上升子序列的长度 == 最少的不上升子序列的划分数
最长不上升子序列的长度 == 最少的上升自学列的划分数
最长下降子序列的长度 == 最少的不下降子序列的划分数
最长不下降子序列的长度 == 最少的下降子序列的划分数
在递增序列中:
Lower_bound ,第一个大于等于 x 的位置。
Upper_bound, 第一个大于 x 的位置。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int a[N],f[N],s[N];
//对于降序排列的数组 f,二分查找 <x 的第一个数的位置
int find(int l,int r,int k)
{
while(l<r)
{
int mid = (l + r)>>1;
if(f[mid]<k) r=mid;
else l = mid + 1;
}
return r;
}
int main()
{
int x;
while(scanf("%d",&x)!=EOF)
{
if(x) a[++n] = x;
}
//要求最长不上升子序列的长度,就等于最少上升子序列的划分数
int len = 0;
f[0]=0x3f3f3f3f; //注意初值!
for(int i=1;i<=n;i++)
{
if(a[i]<=f[len]) f[++len] = a[i];
else f[upper_bound(f+1,f+len+1,a[i],greater<int>())-f] = a[i];
//寻找到第一个 小于 x 的位置,不能等于。
}
printf("%d\n",len);
//要求最少的不下上升序列的划分数,最后集合中的是最长上升子序列。
int cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]>s[cnt]) s[++cnt] = a[i];
else s[lower_bound(s+1,s+cnt+1,a[i])-s] = a[i];
//寻找到第一个 大于等于 x 的位置,可以等于,因为划分中是不上升序列。
}
printf("%d\n",cnt);
return 0;
}
最少的上升自学列的划分数
大佬,打错字了,是子序列。