思路
dp 我们用f[i]来表示 a[i]可以构成的最长上升子序列
首先服务器托管网 一个数字就是长度为1的序列
所以我们需要将所有的f[i]初始化为1
然后我们考虑状态
比如 f[j]
当指针来到a[j]这个数
前面所有数已经算完固定
则a[j]所能形成的最长上升子序列的条件是
1.a[j]大于前面的数
2.f[i]是小于a[j]里面的数之中子序列最长的
如果满足条件
则f[j]=f[i]+1;加上a[j]这个元素长度加1
模拟例子
当指针来到a【1】
前面没有比他小的数 f[1]=1;
来到a[2]
3>1
f【2】=1;
来到a[3]
1
所以f[2]可以继承1 形成的最长子序列
f[3]=2;
来到最后一个数
其前面小于他且子序列最长的数是5
因此 直接继承5的子序列且长度+1；
因此最终答案为4；
代码
#include
#include
#include
#include
using namespace std;
const int N=1010;
int a[N],f[N];
int main(){
int n;
cin>>n;
for(int i=0;i
cin>>a[i];
f[i]=1;
}
int res=0;
for(int i=0;i
for(int j=0;j
if(a[i]>a服务器托管网[j]){
f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
}
}
}
cout return 0;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: IntelliJ IDEA 一般需要设置什么以及如何设置
在使用 IntelliJ IDEA 时，根据你的个人偏好和项目需求，你可能需要设置一些参数和功能。以下是一些常见的设置项以及如何设置它们的简要说明： 1. 外观和主题 设置方法：File > Settings (或 IntelliJ IDEA > …
