40WA蒟蒻求解

B3637 最长上升子序列

qiao_li_pa @ 2023-10-18 21:09:51

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> a,ranks;//a为题目序列,ranks[i]为i处后最长上升序列长度
int ranked(int);
int main(){
    cin>>n;
    ranks.resize(n+1);
        a.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }//读入数据
    for(int i=n;i>=1;i--){
        ranks[i]=ranked(i); 
    }//将i处的最长上升序列长度赋值入ranks数组
        cout<<ranks[1]<<endl;//输出数据
}
int ranked(int x){//该函数用于确定x处最长上升序列长度
    if(x==n) return 1;//边界判断
    int maxn=1;
    for(int i=x;i<=n;i++){
        if(a[i]>a[x]){
            maxn=max(maxn,ranks[i]+1);
        }//状态转移方程
    }//向后搜索大于a[x]的值
    return maxn;
}

代码如上,带注释,使用的是dp逆推思路,请各位帮忙看看出错在哪


by _zhx @ 2023-10-18 21:15:58

@qiao_li_pa

#include<bits/stdc++.h>
using namespace std;
int n,a[5055],v[5055],x=INT_MIN;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i],v[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i]) v[i]=max(v[i],v[j]+1);//有更大的就更新
            x=max(x,v[i]);//是这一个大还是原来的大
        }
    }
    cout<<x;
    return 0;
}

|