1759:最长上升子序列

题目:

总时间限制:

2000ms

内存限制:

65536kB

描述

一个数的序列

b_i，当

b₁ <

b₂ < ... <

b_S的时候，我们称这个序列是上升的。对于给定的一个序列(

a₁,

a₂, ...,

a_N)，我们可以得到一些上升的子序列(

a_i1,

a_i2, ...,

a_iK)，这里1 <=

i₁ <

i₂ < ... <

i_K <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出

最长上升子序列的长度。

样例输入

71 7 3 5 9 4 8

样例输出                4 下面放一下ac代码

#include
        
         #define ll long longusing namespace std;const ll maxn=1000+10;ll f[maxn];//用来递推的数组ll a[maxn];//存储输入数据int main(){    ll n;    cin>>n;    for(ll i=1;i<=n;i++)    {        scanf("%lld",&a[i]);//输入数据        f[i]=1;//顺便为f数组赋初值        /*        f数组的意义是以a[i]结尾的序列能拥有的最大长度        */    }    for(ll i=2;i<=n;i++)//i=1时f[1]肯定等于1,所以从2开始        for(ll j=1;j<=i-1;j++)//j代表枚举f[i]前面的所有可能        {            if(a[i]>a[j])//如果可以加在它后面,记住这里的子序列是可以间断的                f[i]=max(f[i],f[j]+1);        }    ll ans=f[1];//为ans初定义    for(ll i=2;i<=n;i++)//这里的意思是找出f[i=1~n]的最大值        if(f[i]>ans)            ans=f[i];    cout<
         
          <
         
        

 

然后开始解释一下这道题

我们建立一个数组f[maxn],

f数组的意义是以a[i]结尾的序列能拥有的最大上升长度

毫无疑问f[1]始终=1,然后我们对其他f[i]也都赋初始值为1,因为,如果f[i]就只包括a[i]一个的话长度就是1呀

然后核心是状态转移方程

 if(a[i]>a[j])//如果可以加在它后面,记住这里的子序列是可以间断的

               

f[i]=max(f[i],f[j]+1); 先说明j=1~i-1,因为a[i]只能拼接在它前面的序列嘛,所以j最大为i-1 解释一下这段代码:

if(a[i]>a[j])就是说可以拼接,因为符合上升条件 然后f[i]=max(f[i],f[j]+1);这里这段语句可能会执行几次,所以有f[i]=max(f[i],....)这样的东西,就是

新的自己和旧的自己比较的意思,我们平时用的a=a+1,也是这样,两个a不一样,a=a+1这个栗子是教练教我的,讲的真好 然后f[i]=max(f[i],f[j]+1)的意思就是在前面已经判断了可以拼接的基础上,如果加在前面的f[j]序列上更长的话就f[i]=f[j]+1(+1的意思是

相对于前面的f[j]长度又多了一个,也就是多了a[i]),

否则就f[i]=f[i]不变

推荐一道类似的题目: