[CODEVS] 2185 最长公共上升子序列

把LIS和LCS的状态结合，f[i][j]表示 a的前i位，和b以b[j]结尾的子序列 的LICS。

1. a[i]==b[j] 那么f[i][j]=max{f[i-1][k]}+1 其中1<=k<j，满足b[k]<b[j]
2. a[i] != b[j] 那么f[i][j]=f[i-1][j]

对此我的理解是 ，i递增是转移的深入，j遍历是保证递增的性质。

定义决策集合为[1,j-1]中b[j]<b[i]的值，我们需要最大值。
对于内层循环，外层提供的i是固定的，而a[i]==b[i]，所以在集合内的元素不会退出，也就是前面的可以为后面服务。

而对于j-1位转移到了j位，决策集合只需要最大值，那么判断b[j]和mx的关系决定是否加入即可，可以省下一层找最大值的循环，

//Stay foolish,stay hungry,stay young,stay simple
#include<iostream>
using namespace std;

int f[3001][3001];
int a[3001],b[3001];
int n,m;

int main(){
    cin>>n;
    m=n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>b[i];
    for(int i=1;i<=n;i++){
        int mx=0;
//      if(b[0]<a[i]) mx=f[i-1][0];
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]) f[i][j]=mx+1;
            else f[i][j]=f[i-1][j];
            if(b[j]<a[i]) mx=max(mx,f[i-1][j]);
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++) ans=max(ans,f[n][i]);
    cout<<ans<<endl;
    return 0;
}