J - Virus UVA - 12511——最长上升递增子序列

小咪咪 2022-06-14 04:11 113阅读 0赞

Think:  
1题目理解：T组测试数据，每组测试数据输入两串字符，求最大上升递增子序列  
2思考：dp：通过状态转移方程优化节省内层一层for循环？

[建议参考博客][Link 1]  
参考：  
题目大意：T种情况，每种情况2行数据，每行数据第一个表示个数，接下来是一个序列，问两组数据的最长公共递增子序列的长度。  
解题思路：当看到这题想到的是LCS和LIS问题，没错这题也是动态规划问题，只要找到状态转移方程就可轻易搞定！  
　　　　　>\_<:LIS设DP\[i\]表示以第i个数字结尾的最长上升子序列的长度  
　　　　　>0<:DP\[i\]=max(DP\[j\]+1)\{1<=j<=i-1\}  
　　　　 >\_<:LCS设DP\[i\]\[j\]表示以A串第i个字符结尾以B串第j个字符结尾的最长字串  
　　　　　>0<:当a\[i\]==b\[j\]时：DP\[i\]\[j\]=DP\{i-1\]\[j-1\]+1;  
　　　　　　　当a\[i\]!=b\[j\]时：DP\[i\]\[j\]=max(DP\[i-1\]\[j\],DP\[i\]\[j-1\])  
　　　　　>\_<:LCIS设F\[i\]\[j\]表示以a串前i个字符b串的前j个字符且以b\[j\]为结尾构成的LCIS的长度  
　　　　　>0<:当a\[i\]!=b\[j\]时：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\]

[vjudge题目链接][vjudge]

以下为Accepted代码——借鉴+\_dp——70ms

#include <bits/stdc++.h>
    
    using namespace std;
    
    int f[1004][1004], a[1004], b[1004];
    
    int main(){
        int T, n, m, i, j;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            for(i = 1; i <= n; i++)
                scanf("%d", &a[i]);
            scanf("%d", &m);
            for(i = 1; i <= m; i++)
                scanf("%d", &b[i]);
    
            memset(f, 0, sizeof(f));
            for(i = 1; i <= n; i++){
                int mav = 0;
                for(j = 1; j <= m; j++){
                    if(a[i] > b[j] && mav < f[i-1][j])/*更新mav*/
                        mav = f[i-1][j];
    
                    if(a[i] != b[j])
                        f[i][j] = f[i-1][j];
                    else if(a[i] == b[j])
                        f[i][j] = mav + 1;
                }
            }
            int mav = 0;
            for(i = 1; i <= m; i++)
                mav = max(mav, f[n][i]);
            printf("%d\n", mav);
        }
        return 0;
    }

以下为Accepted代码——借鉴+\_暴力——440ms

#include <bits/stdc++.h>
    
    using namespace std;
    
    int f[1004][1004], a[1004], b[1004];
    
    int main(){
        int T, n, m, i, j, k;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            for(i = 1; i <= n; i++)
                scanf("%d", &a[i]);
            scanf("%d", &m);
            for(i = 1; i <= m; i++)
                scanf("%d", &b[i]);
    
            memset(f, 0, sizeof(f));
            for(i = 1; i <= n; i++){
                for(j = 1; j <= m; j++){
    
                    if(a[i] != b[j])
                        f[i][j] = f[i-1][j];
                    else if(a[i] == b[j]){
                        int mav = 0;
                        for(k = 1; k < j; k++)
                            if(b[k] < b[j])
                                mav = max(mav, f[i-1][k]);
                        f[i][j] = mav + 1;
                    }
                }
            }
            int mav = 0;
            for(i = 1; i <= m; i++)
                mav = max(mav, f[n][i]);
            printf("%d\n", mav);
        }
        return 0;
    }

[Link 1]: http://www.cnblogs.com/zjutlitao/p/3650930.html
[vjudge]: https://vjudge.net/contest/166701#problem/J