思路:
(1)条件:n个数
(2)问题:
- 求最长递减子序列长度;
- 最少拆分为多少个递减子序列
(3)分析:
- dp : O(n^2);
- f[i]描述长度为i的序列尾部最小值,每次用二分找到新值a[i]可以更新哪个长度,并更新即可; : O(nlog(n));
- dilworth定理:最长链元素数目等于反向链最小划分数目;
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n,ans,a[N],f[N];//这里把f数组与len数组合并了
int main()
{
cin.tie(0);
cout.tie(0);//必须加速优化
int x;
while(cin>>x)a[++n]=x;
memset(f,0x3F,sizeof(f));//初始化为极大值
reverse(a+1,a+n+1);//反转
for(int i=1;i<=n;i++)
{
int l=1,r=i;
while(l<r)//左查
{
int mid=(l+r)/2;
if(f[mid]>a[i])r=mid;
else l=mid+1;
}
f[l]=min(f[l],a[i]);
ans=max(ans,l);
}
cout<<ans<<endl;
memset(f,0x3F,sizeof(f));
reverse(a+1,a+n+1);//反转回来
ans=0;//注意
for(int i=1;i<=n;i++)
{
int l=1,r=i;
while(l<r)
{
int mid=(l+r)/2;
if(f[mid]>=a[i])r=mid;
else l=mid+1;
}
f[l]=min(f[l],a[i]);
ans=max(ans,l);
}
cout<<ans<<endl;
return 0;
}