蓝桥杯打卡Day11

文章目录

最长上升子序列
最长上升子序列II

一、最长上升子序列IO链接

本题思路:本题是一关于dp问题中的一个类型是最长上升子序列问题，首先我们将状态表示出来：f[i]表示以a[i]结尾的最大的上升序列。状态计算（集合划分）：j∈(0,1,2,..,i-1),a[i]>a[j]，f[i] = max(f[i], f[j] + 1)。最后在找f[i]的最大值。

#pragma G++ optimize("Ofast,no-stack-protector");
#include<bits/stdc++.h>

using namespace std;

#define ios() ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define rep3(j,b,m) for(int j=b;j<m;j++)
#define rep4(j,b,m) for(int j=b;j<=m;j++)
typedef long long LL;

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}

constexpr int N=1010;

int n;
int a[N];
int f[N];

int main()
{
    ios();
    
    n=read();
    
    rep2(i,1,n) a[i]=read();
    
    /*状态表示：f[i]表示以a[i]结尾的最大的上升序列。
    状态计算（集合划分）：j∈(0,1,2,..,i-1), 
    a[i]>a[j]
    f[i] = max(f[i], f[j] + 1)。
    最后在找f[i]的最大值。
    */
    int ans=0;
    rep2(i,1,n){
        f[i]=1;//最小的就是自己为1
        rep3(j,1,i)
            if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    
    
    print(ans);
    return 0;
}

N=1010

#初始化dp数组为1
#表示以第i个字符结尾最长上升子序列长度
dp=[1]*N

n=int(input())
a=[int(x) for x in input().split()]

for i in range(n):
  for j in range(i):
    if a[j]<a[i]:
      dp[i]=max(dp[i],dp[j]+1)

print(max(dp))

二、最长上升子序列IIIO链接

本题思路:上面问题的优化写法，对于数据量很大时可以考虑二分优化，首先找到一个最大的小于等于当前数的数, 我们可以用二分来优化，先定义边界，l = 0, r = len, 其中len是q数组的长度
通过q[r + 1] = a[i]来将x覆盖a的值，即r + 1 > len时, 表示超出了二分边界，这时就要len ++更新q的长度。文章来源地址https://uudwc.com/A/20jzN

#include <bits/stdc++.h>

constexpr int N=100010;

int n;
int a[N],q[N];

int binary_search(int l,int r,int x)
{
  while(l<r){
    int mid=l+r+1>>1;
    if(q[mid]<x) l=mid;
    else r=mid-1;
  }
  return l;
}

int main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);std::cout.tie(nullptr);
  
  std::cin>>n;
  for(int i=0;i<n;i++) std::cin>>a[i];
  
  int len=0;
  for(int i=0;i<n;i++){
    int l=0,r=len;
    int k=binary_search(l,r,a[i]);//找出第一个小于等于当前的数
    len=std::max(len,k+1);//此时k+1超出len，则需要更新len
    q[k+1]=a[i];
  }
  
  std::cout<<len<<std::endl;
  return 0;
}

N=100010

q=[0]*N

n=int(input())
a=[int(x) for x in input().split()]

len=0
for i in range(n):
  l=0
  r=len
  while l<r:
    mid=(l+r+1)//2
    if q[mid]<a[i]: 
      l=mid
    else:
      r=mid-1
  len=max(len,r+1)
  q[r+1]=a[i]

print(len)