HDOJ 1423 Greatest Common Increasing Subsequence 【DP】【最长公共上升子序列】

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 8768 Accepted Submission(s): 2831

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

题意

找出两个序列中的最长公共上升子序列

思路

动态规划

假如 a[i] != b[j]

那么毫无疑问 a[i] 对这个LCIS是毫无贡献的 所以 dp[i][j] = dp[i - 1][j];

如果a[i] == b[j]

那么 这个最长公共上升子序列的长度至少为1 并且 找出前面可以接的最长的LCIS的长度 + 1 就可以了

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <cstdlib>
#include <ctype.h>
#include <numeric>
#include <sstream>
using namespace std;

typedef long long LL;
const double PI = 3.14159265358979323846264338327;
const double E = 2.718281828459;
const double eps = 1e-6;
const int MAXN = 0x3f3f3f3f;
const int MINN = 0xc0c0c0c0;
const int maxn = 1e2 * 5 + 5;
const int MOD = 1e9 + 7;
int a[maxn], b[maxn], dp[maxn][maxn];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        scanf(" %d", &n);
        int i, j, k;
        for (i = 0; i < n; i++)
            scanf("%d", &a[i]);
        scanf("%d", &m);
        for (i = 0; i < m; i++)
            scanf("%d", &b[i]);
        memset(dp, 0, sizeof(dp));
        int ans = 0;
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < m; j++)
            {
                if (a[i] == b[j])
                {
                    int max_dp = 0;
                    for (k = 0; k < j; k++)
                    {
                        if (dp[i][k] > max_dp && b[j] > b[k])
                            max_dp = dp[i][k];
                    }
                    dp[i][j] += max_dp + 1;
                }
                else if (i)
                    dp[i][j] = dp[i - 1][j];
                if (dp[i][j] > ans)
                    ans = dp[i][j];
            }
        }
        cout << ans << endl;
        if (t)
            cout << endl;
    }
}

优化代码

#include <iostream>             //时间优化
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <cstdlib>
#include <ctype.h>
#include <numeric>
#include <sstream>
using namespace std;

typedef long long LL;
const double PI = 3.14159265358979323846264338327;
const double E = 2.718281828459;
const double eps = 1e-6;
const int MAXN = 0x3f3f3f3f;
const int MINN = 0xc0c0c0c0;
const int maxn = 1e2 * 5 + 5;
const int MOD = 1e9 + 7;
int a[maxn], b[maxn], dp[maxn][maxn];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        scanf(" %d", &n);
        int i, j, k;
        for (i = 0; i < n; i++)
            scanf("%d", &a[i]);
        scanf("%d", &m);
        for (i = 0; i < m; i++)
            scanf("%d", &b[i]);
        memset(dp, 0, sizeof(dp));
        int ans = 0;
        int max_dp;
        for (i = 0; i < n; i++)
        {
            max_dp = 0;
            for (j = 0; j < m; j++)
            {
                if (i)
                    dp[i][j] = dp[i - 1][j];
                if (a[i] > b[j] && dp[i][j] > max_dp)
                    max_dp = dp[i][j];
                if (a[i] == b[j])
                    dp[i][j] = max_dp + 1;
                if (dp[i][j] > ans)
                    ans = dp[i][j];
            }
        }
        cout << ans << endl;
        if (t)
            cout << endl;
    }
}