HDU1423：Greatest Common Increasing Subsequence(LICS)-白红宇

HDU1423：Greatest Common Increasing Subsequence(LICS)

阅读量：5958 次

发布时间：2019-06-19

本文共 1143 字，大约阅读时间需要 3 分钟。

Problem Description

This is a problem from ZOJ 2432.To make it easyer,you just need output the length of the subsequence.

Input

Each sequence is described with M - its length (1 <= M <= 500) and M integer numbers Ai (-2^31 <= Ai < 2^31) - the sequence itself.

Output

output print L - the length of the greatest common increasing subsequence of both sequences.

Sample Input

      1 5 1 4 2 5 -12 4 -12 1 2 4 

Sample Output

2

题意：求最长递增公共子序列的长度

思路：直接模板

#include 
    
     #include 
     
      #include 
      
       using namespace std;int n,m,a[505],b[505],dp[505][505];int LICS(){    int MAX,i,j;    memset(dp,0,sizeof(dp));    for(i = 1; i<=n; i++)    {        MAX = 0;        for(j = 1; j<=m; j++)        {            dp[i][j] = dp[i-1][j];            if(a[i]>b[j] && MAX

上面的虽然可以解决，但是二维浪费空间较大，我们注意到在LICS函数中有一句dp[i][j] = dp[i-1][j]，这证明dp数组前后没有变化！于是可以优化成一维数组！

#include 
    
     #include 
     
      #include 
      
       using namespace std;int a[505],b[505],dp[505],n,m;int LICS(){    int i,j,MAX;    memset(dp,0,sizeof(dp));    for(i = 1; i<=n; i++)    {        MAX = 0;        for(j = 1; j<=m; j++)        {            if(a[i]>b[j] && MAX