AcWing 272. 最长公共上升子序列

原题连接：https://www.acwing.com/problem/content/description/274/

谁能想到这么表示状态？？？

优化

/* 状态表示： f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合； f[i][j]的值等于该集合的子序列中长度的最大值； 状态计算（对应集合划分）： 首先依据公共子序列中是否包含a[i]，将f[i][j]所代表的集合划分成两个不重不漏的子集： 不包含a[i]的子集，最大值是f[i - 1][j]； 包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b[]中是哪个数： 子序列只包含b[j]一个数，长度是1； 子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1； … 子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1； 边界： 初始化： f[0][1...n] = 0, f[1...n][0] = 0; 答案： max(f[n][1...n]) */
#include <iostream>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main()
{
    
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
    
    // 这个最内层循环可以优化一下
    // for (int i = 1; i <= n; i ++)
    // for (int j = 1; j <= n; j ++ )
    // {
    
    // //a[i] != b[j]
    // f[i][j] = f[i - 1][j];
    // // a[i] = b[j]
    // if(a[i] == b[j])
    // {
    
    // int maxv = 1;
    // for (int k = 1; k <= j - 1; k ++ )
    // if (b[k] < b[j])
    // maxv = max(maxv, f[i - 1][k] + 1);
    // f[i][j] = max(maxv, f[i][j]);
    // }
    // }
    
     for (int i = 1; i <= n; i ++)
     {
    
        // 额，确实可以这样优化，因为只有b[j] = a[i]的时候，
        // f[i][j]才会变大，此时，用maxv就行了，maxv代表前缀上升子序列最大长度
        // 这里的maxv就变味了。和上边的意思不一样了。
        int maxv = 1;
        for (int j = 1; j <= n; ++ j)
        {
    
            f[i][j] = f[i - 1][j];
            if (b[j] == a[i]) f[i][j] = max(f[i][j], maxv);
            if (b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);
        }
     }
     
        
    
    int res = 0;
    // 为啥结果是枚举b[i], 因为你看状态定义，不能枚举a[i]
    // 按照状态定义，不一定b[n]一定取到，但是a[n]是肯定的
    for(int i = 1; i <= n; i ++) res = max(res, f[n][i]);
    cout << res << endl;
    
    return 0;
}