cancan1030 @ 2024-02-06 09:44:21

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N],b[N],cnt; 
int main(){
    int n;
    cin>>n;
    memset(b,N,sizeof(b));
    b[0]=b[1]=-N;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1,j=0;i<=n;i++){
        if(a[i]<b[j]&&a[i]>b[j-1]){
            b[j]=a[i];
//          for(int k=1;k<=n;k++){
//              cout<<b[k]<<" ";
//          }
//          cout<<endl;
        }
        else if(a[i]>b[j]){
//          cout<<a[i+1]<<" ";
            b[++j]=a[i];
//          for(int k=1;k<=n;k++){
//              cout<<b[k]<<" ";
//          }
//          cout<<endl;
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
} 

by Michelle01 @ 2024-02-06 10:01:58

@cancan1030 这一题用你的这种模拟去找最长上升子序列不太好写。你可以试一下用动态规划

by Michelle01 @ 2024-02-06 10:06:08

@cancan1030 用不到二分栈，用普通的动态规划就行```

include <stdio.h>

include<algorithm>

include<math.h>

include<bits/stdc++.h>

using namespace std;

int main(){

int n;
int ans = 0;
cin >> n;
int dp[100010];
int a[100010];
for(int i = 1; i <= n; i++){
    cin >> a[i];
}
for(int i = 1; i <= n; i++){
    dp[i] = 1;
    for(int j = 1; j <= i - 1; j++){
        if(a[j] < a[i]){
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}
for(int i = 1; i <= n; i++){
    ans = max(ans, dp[i]);
}
cout << ans;

return 0;

}

by cancan1030 @ 2024-02-06 10:06:46

@Michelle01 动归的我会写，就是二分栈的更快，我想尝试一下

by Michelle01 @ 2024-02-06 10:08:03

@cancan1030 二分栈里面是有弹出操作的，我没看到你的代码里有。（也许我没看懂你的代码）

by Michelle01 @ 2024-02-06 10:08:55

@cancan1030 你那个b数组相当于一个栈是吧

by cancan1030 @ 2024-02-06 10:09:37

@Michelle01 我这道题AC过，这次主要是想知道这道题用二分栈怎么写

by cancan1030 @ 2024-02-06 10:09:48

@Michelle01 谢谢

by cancan1030 @ 2024-02-06 10:11:06

@Michelle01 嗯对

by Michelle01 @ 2024-02-06 10:26:47

@cancan1030 你的b数组压栈的意义是什么

by cancan1030 @ 2024-02-06 10:32:10

@Michelle01 就是如果x比栈顶元素大就让x入栈，最长上升子序列长度加1