最长公共上升子序列

Greatest Common Increasing Subsequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3362    Accepted Submission(s): 1060


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

自己写的公式，min也是自己想到的，哈哈，太高兴了

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<string>
#include<algorithm>
#define MAX 502
using namespace std;
int dp[MAX][MAX];
int a[MAX], b[MAX];
int main()
{
    int T, m, n, min;
    cin >> T;
    while (T--){
        cin >> m;
        for (int i = 0; i < m; i++){
            cin >> a[i];
        }
        cin >> n;
        for (int i = 0; i < n; i++){
            cin >> b[i];
        }
        min = INT_MIN;
        fill(dp[0], dp[0] + n, 0);
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (a[i] == b[j] && a[i]>min){
                    min = a[i];
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }
                else{
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        cout << dp[m][n] << endl;
        if (T){
            cout << endl;
        }
    }
    
    return 0;
}