noip-最长上升子序列

作者: admin
标签: 线性dp
更新: 7/10/2019, 2:02:05 PM

题目:最长上升子序列

这是一道入门级动态规划题目,让我们尝试分析一波。

分析:

此处首先划分一下子问题,我们求解动态规划这类问题,首先可以划分一下子问题,再去找状态转移方程,最后写代码。

子问题:如果第n项能够与第n-1项的最长子序列构成一个更长子序列,那么第n项的最长子序列就是第n-1项的最长子序列加1,第一项的最长子序列是1。

状态转移方程: 设f[n]保存第n个数的最长序列,数组a保存数据

f[i] = max(f[i],f[i-1]+1) if a[i] > a[i-1] else f[i]=1

c++代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 1000
int s[MAX];
int f[MAX];
int main(){
    int n;
    cin >> n;
    memset(s, 0, sizeof(s));
    memset(f,0,sizeof(f));
    for(int i = 0; i < n; i++){
        cin >> s[i];
        f[i]=1;
    }
    for(int i = 0; i < n - 1; i++)
        for(int j = i + 1; j < n; j++)
            if(s[i] < s[j]) f[j] = max(f[j], f[i] + 1);//填充第n项的最长序列长度
    cout <<*max_element(f,f+n)<< endl; //n个状态中的最大值
    return 0;
}
删除
修改
点击登陆评论