https://www.luogu.org/problemnew/show/P1020
C++版本一
STL+二分+DP
题解：求一个序列里面最少有多少最长不上升序列等于求这个序列里最长上升序列的长度。我们用f[x]数组（第一问）来记录当前长度为x的不上升序列中最大的结束点（这个运用了贪心的思想），如果当前数小于等于当前的最长不上升序列的结束点，那么我们把当前最长的不上升序列长度加一，把当前数作为这个 不下降序列的结束点，不然我们就用二分查找（为什么可以呢？这是因为我们运用了贪心的思/想后能保证长度越大的不上升序列结束点越小），试着用当前数去更新长度为x的不上升序列的结束点（又是贪心的思想，只更新长度最长且结束点小于自己的），然后第二问你再反着做就行了（把大于等于改为小于）
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=100000+100;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int a[N];
int f[N],l[100005];
struct cmp{bool operator()(int a,int b){return a>b;}};
int main()
{
#ifdef DEBUG
freopen("input.in.txt", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
while(scanf("%d",&a[++n])!=EOF);
n--;
int con=1,cont=1;
l[1]=f[1]=a[1];
for(int i=2;i<=n;i++)
{
if(l[cont]>=a[i])
l[++cont]=a[i];
else
l[upper_bound(l+1,l+cont+1,a[i],cmp())-l]=a[i];
if(f[con]<a[i])
f[++con]=a[i];
else
f[lower_bound(f+1,f+con+1,a[i])-f]=a[i];
}
cout<<cont<<" "<<con;
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
二分+DP
#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=100005;
int a[maxn];
int f[maxn];
int main()
{
int n=0;
int l,r,mid;
while(scanf("%d",&a[++n])!=EOF)continue;
n--;
f[0]=1234123412;//这个数要大于50000，不然可能你就无法更新
int ans1=0;
for(int i=1;i<=n;i++){
if(f[ans1]>=a[i]){
f[ans1+1]=a[i];//结束点为a[i]
ans1++; //当前最长不上升序列的长度加一
}
else {//二分查找
l=0;r=ans1;
while(l<r){
mid=(l+r)/2;
if(f[mid]>=a[i])l=mid+1;
else {
r=mid;
}
}
if(l!=0)f[l]=a[i];
}
}
cout<<ans1<<endl;//输出第一问的答案
memset(f,-1,sizeof(f));//这次前面要尽量小了，不然又无法更新
int ans2=0;
for(int i=1;i<=n;i++){
if(f[ans2]<a[i]){
f[ans2+1]=a[i];//结束点为a[i]
ans2++; //当前最长上升序列长度加一
}
else {//二分查找
l=0;r=ans2;
while(l<r){
mid=(l+r)/2;
if(f[mid]>=a[i])r=mid;
else {
l=mid+1;
}
}
f[l]=a[i];
}
}
cout<<ans2<<endl;//输出第二个答案
} C++版本三
树状数组
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1000000];
int z[1000000];
int lowbit(int x)
{
return x&-x;
}
int big;
inline int ask(int x)//这是用来求单调上升子序列的
{
int r=0;
for(int i=x;i>0;i-=lowbit(i))
r=max(r,f[i]);
return r;
}
inline void add(int x,int v)//这也是用来求单调上升子序列的
{
for(int i=x;i<=big;i+=lowbit(i))
f[i]=max(f[i],v);
}
inline int que(int x)//这是用来求最长单调不升子序列的
{
int r=0;
for(int i=x;i<=big;i+=lowbit(i))
r=max(r,f[i]);
return r;
}
inline void psh(int x,int v)//这也是用来求最长单调不升子序列的
{
for(int i=x;i>0;i-=lowbit(i))
f[i]=max(f[i],v);
}
int tot;
int a[1000000];
int ans;
int main()
{
tot=1;
while(scanf("%d",&a[tot])!=EOF)
{
big=max(big,a[tot]);
z[tot]=a[tot];
tot++;
}
tot--;//读入并统计个数
for(int i=1;i<=tot;i++)//求最长单升子序列，树状数组中保存的是0~a[i]的最大值
{
int x=ask(a[i])+1;
ans=max(ans,x);
add(a[i]+1,x);//因为是严格单升所以这里要+1
}
memset(f,0,sizeof(f));//清空树状数组，用来求下面的不降子序列
int num=0;
for(int i=1;i<=tot;i++)//求最长不降子序列，树状数组里存的是a[i]~inf的最大值
{
int x=que(a[i])+1;
num=max(num,x);
psh(a[i],x);//因为是不升而不是严格单降所以不用-1或+1
}
printf("%d\n%d",num,ans);
return 0;
} C++版本四
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n=0,a[100001],f[100001],d[100001],ans=1,t=0;
int main() {
while(~scanf("%d",&a[++n]));//读入数据方法
n--;//n是导弹数，由于某些原因要--
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=t; j>0; j--)
if(a[i]<=a[d[j]]) {
f[i]=f[d[j]]+1;
break;
}
t=max(t,f[i]);
d[f[i]]=i;//简单的维护过程
ans=max(ans,f[i]);
}
printf("%d\n",ans);
ans=1;
t=0;
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=t; j>0; j--)
if(a[i]>a[d[j]]) {
f[i]=f[d[j]]+1;
break;
}
t=max(t,f[i]);
d[f[i]]=i;
ans=max(ans,f[i]);
}
printf("%d",ans);
}
京公网安备 11010502036488号