12.17
洛谷突然黄名?
DP
1. 洛谷 P1020: 最长不上升子序列 (LNIS) 和最小不上升子序列个数.
首先是 LNIS:
朴素 \(O(n^2)\)做法: 从后往前, dp[i]=max(dp[i],dp[j]+1), 满足 i<j&&a[i]>=a[j].
快速 \(O(n\log n)\)做法: 从前往后, 每次找到序列中第一个比它小的数, 更新优化, 具体原理可见: https://blog.csdn.net/wqtltm/article/details/81253935, 看图相当不错. 同样发现这些数组可以进行复用, 因此只需要一个 d 数组即可, 空间复杂度 $O(n)$.
其次是最小划分出序列的个数.
有一个 Dilworth 定理, 简单来讲就是, 最小不上升子序列个数 = 最长上升子序列长度(把不去掉, 把个数换成长度). 其实感性是可以理解的.
那么再跑一个 LIS 即可.
注意: 找第一个比他小的数, 可以用 upper_bound(a+1,a+n+1,x,greater<int>())来做, 不要用 lower_bound()+1, 容易出锅. 小于等于同理.
- #include<bits/stdc++.h>
- using namespace std;
- const int M=1e5+20;
- int cnt,a[M];
- struct LNIS{
- int dp[M],n;
- void init(){n=cnt;}
- void run(){
- int ans=0;
- for(int i=n;i>=1;--i){
- dp[i]=1;
- for(int j=n;j>=i+1;--j)
- if (a[i]>=a[j])
- dp[i]=max(dp[i],dp[j]+1);
- ans=max(ans,dp[i]);
- }
- printf("%d\n",ans);
- }
- }L1;
- struct LIS{
- int dp[M],n;
- void init(){n=cnt;}
- void run(){
- int ans=0;
- for(int i=1;i<=n;++i){
- dp[i]=1;
- for(int j=1;j<=i-1;++j)
- if (a[i]>a[j])
- dp[i]=max(dp[i],dp[j]+1);
- ans=max(ans,dp[i]);
- }
- printf("%d\n",ans);
- }
- }L2;
- int main(){
- int c;
- while(~scanf("%d",&c))
- a[++cnt]=c;
- L1.init();
- L2.init();
- L1.run();
- L2.run();
- return 0;
- }
nlogn 做法:
- #include<bits/stdc++.h>
- using namespace std;
- const int M=1e5+20;
- int cnt,a[M];
- struct LNIS{
- int dp[M],d[M],n;
- void init(){n=cnt;}
- void run(){
- int len=1;
- for(int i=1;i<=n;++i){
- int p=upper_bound(d+1,d+len+1,a[i],greater<int>())-d;// 找到第一个小于 a[i]的下标
- dp[i]=p,d[p]=a[i];
- if (p>len)
- len=p;
- }
- int ans=0;
- for(int i=1;i<=n;++i)
- ans=max(ans,dp[i]);
- printf("%d\n",ans);
- }
- }L1;
- struct LIS{
- int dp[M],d[M],n;
- void init(){n=cnt;}
- void run(){
- int len=0;
- for(int i=1;i<=n;++i){
- int p=lower_bound(d+1,d+len+1,a[i])-d;// 找到第一个大于等于 a[i]的下标
- dp[i]=p,d[p]=a[i];
- if (p>len)
- len=p;
- }
- int ans=0;
- for(int i=1;i<=n;++i)
- ans=max(ans,dp[i]);
- printf("%d\n",ans);
- }
- }L2;
- int main(){
- int c;
- while(~scanf("%d",&c))
- a[++cnt]=c;
- L1.init();
- L2.init();
- L1.run();
- L2.run();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3343961.html