Greatest Common Increasing Subsequence

ACM暑期集训队练习赛（二） 

题意：

就是一个求LCIS的典型题，主要是搞懂LCIS的动态规划求法。

定义状态：F[i][j]表示以a串的前i个整数与b串的前j个整数且以b[j]为结尾构成的LCIS的长度。

状态转移方程：

①F[i][j] = F[i-1][j] (a[i] != b[j])

②F[i][j] = max(F[i-1][k]+1) (1 <= k <= j-1 && b[j] > b[k])

现在我们来说为什么会是这样的状态转移方程呢？

对于①，因为F[i][j]是以b[j]为结尾的LCIS，如果F[i][j]>0那么就说明a[1]..a[i]中必然有一个整数a[k]等于b[j],因为a[k]!=a[i]，那么a[i]对F[i][j]没有贡献，于是我们不考虑它照样能得出F[i][j]的最优值。所以在a[i]!=b[j]的情况下必然有F[i][j]=F[i-1][j]。

对于②，前提是a[i] == b[j],我们需要去找一个最长的且能让b[j]接在其末尾的LCIS。之前最长的LCIS在哪呢？首先我们要去找的F数组的第一维必然是i-1。因为i已经拿去和b[j]配对去了，不能用了。并且也不能是i-2，因为i-1必然比i-2更优。第二维呢？那就需要枚举b[1]...b[j-1]了，因为你不知道这里面哪个最长且哪个小于b[j]。这里还有一个问题，可不可能不配对呢？也就是在a[i]==b[j]的情况下，需不需要考虑F[i][j]=F[i-1][j]的决策呢？答案是不需要。因为如果b[j]不和a[i]配对，那就是和之前的a[1]...a[j-1]配对（假设F[i-1][j]>0，等于0不考虑），这样必然没有和a[i]配对优越。（为什么必然呢？因为b[j]和a[i]配对之后的转移是max(F[i-1][k])+1，而和之前的i`配对则是max(F[i`-1][k])+1。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1001;  
  
int a[MAXN], b[MAXN];  
int f[MAXN];  
int n, m;  
  
void init()  
{  
    memset(f, 0, sizeof(f));  
}  

int max(int a,int b)
{
    return a>b?a:b;
}

void dp()  
{  
    init();  
    for(int i = 1; i <= n; i++)  
    {  
        int MAX = 0;  
        for(int j = 1; j <= n; j++)  
        {  
            if(a[i] > b[j]) MAX = max(MAX, f[j]);  
            if(a[i] == b[j]) f[j] = MAX+1;  
        }  
    }  
    int ans = 0;  
    for(int j = 1; j <= m; j++) ans = max(ans, f[j]);  
    printf("%d\n", ans);  
}  

int main()  
{  
   // freopen("in.txt","r",stdin);
    int T;  
    scanf("%d",&T);  
    for(int t=1;t<=T;t++)  
    {  
        scanf("%d",&n);  
        for(int i=1;i<=n;i++) {scanf("%d",&a[i]);}  
        scanf("%d",&m);  
        for(int i=1;i<=m;i++) {scanf("%d",&b[i]);}  
        dp();
        if(t!=T) cout<<endl;  
    }  
    return  0;  
}