蓝桥杯打卡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
 
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
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define rep3(j,b,m) for(int j=b;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]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]
      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的长度。

#include 
 
constexpr int N=100010;
 
int n;
int a[N],q[N];
 
int binary_search(int l,int r,int x)
{
  while(l
    int mid=l+r+1>>1;
    if(q[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>a[i];
  
  int len=0;
  for(int i=0;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<
  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
    mid=(l+r+1)//2
    if q[mid]
      l=mid
    else:
      r=mid-1
  len=max(len,r+1)
  q[r+1]=a[i]
 
print(len)
 

---