[codevs1576]最长严格上升子序列

#include <iostream>
using namespace std;

int n,maxn,a[5000],dp[5000];

int main() {
    cin>>n;
    
    for(int i=0;i<n;i++) {
        cin>>a[i];    
        dp[i] = 1; 
    }
    
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            if(a[j]<a[i])
                dp[i] = dp[i]>dp[j]+1?dp[i]:dp[j]+1;
                /*
                  这里的dp数组储存的是子序列长度 
                */ 
                
    for(int i=0;i<n;i++)
        if(dp[i]>maxn) 
            maxn = dp[i];
    
    cout<<maxn;
    
    return 0;
}

思路就是建立两个数组,一个储存数据另一个储存链接长度,链接最大的即为最长XX序列。本题属于动态规划基础题,难度不大但贵在思维。

Last modification:March 17th, 2019 at 11:47 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment