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;
}