熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们研究最长公共上升子序列了。 小沐沐说,对于两个数列A和B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这一段数是两个数列的公共上升子序列,而所有的公共上升子序列中最长的就是最长公共上升子序列了。 奶牛半懂不懂,小沐沐要你来告诉奶牛什么是最长公共上升子序列。不过,只要告诉奶牛它的长度就可以了。数列A和B的长度均不超过3000。

输入描述:

第一行N,表示A,B的长度。 第二行,串A。 第三行,串B。

输出描述:

输出长度。

示例1

输入

4
2 2 1 3
2 1 2 3

输出

2

示例2

输入

100
-10 -17 3 -95 -18 -63 103 278 104 226 212 96 242 -18 -14 57 138 248 190 106 -55 55 128 -36 226 78 124 221 43 289 -36 213 124 149 238 249 102 183 266 63 38 160 119 -93 -87 151 286 137 -46 71 206 213 234 66 -78 232 167 150 112 299 32 240 68 289 160 255 205 232 218 90 149 0 28 212 278 79 70 238 11 -92 -84 -82 101 26 106 143 -16 95 265 217 117 230 63 226 113 219 -21 21 6 197 
81 50 32 80 194 246 -85 -37 257 -83 211 191 273 229 -20 226 83 229 115 107 158 -82 212 151 287 16 157 170 100 144 147 -70 -28 88 276 249 98 111 221 81 33 251 108 101 217 -75 -23 229 234 124 33 34 97 237 35 131 249 273 31 264 52 263 26 45 26 19 55 -31 -63 -73 83 87 190 -95 48 -100 -21 133 293 91 26 61 -61 -98 200 -66 -5 213 149 221 286 75 3 98 149 167 172 219 195 289 

输出

5

备注: $1 \le N \le 3000$,A,B中的数字不超过 $2^{31}-1$

题目分析

我们设 f(i, j) 为, A[0 ~ i],B[0 ~ j] 中以 B[j] 为末尾元素的的最长公共上升子序列的长度。

对于 A[i],B[j] :

  • A[i] != B[j],f(i, j) = f(i - 1, j)
  • A[i] = B[j],f(i, j) = max{f(i - 1, k), 1}, 其中 k < j
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            dp[i][j] = dp[i - 1][j];
            if(a[i] == b[j]) {
                dp[i][j] = max(dp[i][j], 1);
                for(int k = 1; k < j; ++k) {
                    if(b[k] < a[i]) dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
                }    
            }
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans;

但是这个代码在这个数据量会超时。 优化: 我们可以看到 j 的遍历顺序是从小到大,且 i 不变,那么b[j] < a[i] 不会受影响。我们可以动态维护一个mx

代码实现

#include <iostream>
using namespace std;
const int N = 3e3 + 10;

int n, ans, dp[N][N], a[N], b[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    for(int i = 1; i <= n; ++i) {
        int mx = 1;
        for(int j = 1; j <= n; ++j) {
            dp[i][j] = dp[i - 1][j];
            if(a[i] == b[j]) dp[i][j] = max(dp[i][j], mx);
            if(b[j] < a[i]) mx = max(mx, dp[i - 1][j] + 1);
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans;
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status