【OJ模板和问题记录】——求最长子序列

逃离我推掉我的手 2022-08-29 04:29 141阅读 0赞

### 求最长子序列 ###

*  最长上升子序列长度
 *  最长公共子序列

# 最长上升子序列长度 #

求给定序列的最长上升子序列，子序列不一定是连续的。  
题目地址[POJ2533 Longest Ordered Subsequence][]  
思路：  
动态规划，用dp\[i\]表示以第i个数字结尾的最长子序列，dp\[i\]等于比他小的数字dp\[j\]+1,遍历后找到最大值即可。O(n2)  
代码：

#include <iostream>
    #define maxn 1001
    using namespace std;
    int a[maxn];
    int dp[maxn];
    int main()
    { 
    	cin.sync_with_stdio(0);
    	cin.tie(0);
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++)
        { 
            cin >> a[i];
        }
        int ans = 0;
        for(int i = 1;i<=n;i++)
        { 
            dp[i] = 1;
            for(int j = 1;j < i;j++)
            { 
                if(a[j] < a[i])
                { 
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            ans = max(dp[i],ans);
        }
        cout << ans << endl;
        return 0;
    }

优化：可以用一个辅助数组记录最长上升子序列d\[\],len表示d的长度。每次遇到比d\[len\]大的元素就放到d数组后面，遇到比d\[len\]小的元素替换d数组中第一个比a\[i\]大的值，可以看出这样无法求得最长子序列，但是对于最长序列的长度无影响，替换掉d中的值是因为，在d的长度不被影响的情况下，d中元素越小越可能得到更长的子序列。

#include <iostream>
    #include <algorithm>
    #define maxn 1002
    using namespace std;
    int d[maxn];
    int a[maxn];
    int main()
    { 
    	cin.sync_with_stdio(0);
    	cin.tie(0);
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++)
        { 
            cin >> a[i];
        }
        int len = 1;
        d[1] = a[1];
        for(int i = 2;i <= n;i++)
        { 
            if(d[len] < a[i])
            { 
                d[++len] = a[i];
            }
            else
            { 
                *upper_bound(d+1,d+len+1,a[i]) = a[i];
            }
        }
        cout << len << endl;
        return 0;
    }

# 最长公共子序列 #

[POJ1458][]  
思路：  
用二维数组dp\[i\]\[j\]表示两个字符串s1的前i个字符和s2的前j个字符中最长公共子序列的长度。如果s1的第i个字符和s2的第j个字符相同，那么dp\[i\]\[j\]就是dp\[i-1\]\[j-1\]+1,否则dp\[i\]\[j\]就是max(dp\[i-1\]\[j\],dp\[i\]\[j-1\])  
AC代码：

#include <iostream>
    #include <string>
    #include <cstring>
    #define maxn 5000+1
    using namespace std;
    int dp[maxn][maxn];
    int main()
    { 
    	cin.sync_with_stdio(0);
    	cin.tie(0);
    	string str1,str2;
        while(cin >> str1 >> str2)
        { 
            int leng1 = str1.size();
            int leng2 = str2.size();
            for(int i = 0;i <= leng1; i ++ ) dp[i][0] = 0;
            for(int j = 0;j <= leng2; j ++ ) dp[0][j] = 0;
            for(int i = 1;i <= str1.size();i++)
            { 
                for(int j = 1;j <= str2.size();j++)
                { 
                    if(str1[i-1]==str2[j-1])
                    { 
                        dp[i][j] = dp[i-1][j-1]+1;
                    }
                    else
                    { 
                        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
            cout << dp[str1.size()][str2.size()] << endl;
        }
    
        return 0;
    }

[POJ2533 Longest Ordered Subsequence]: http://poj.org/problem?id=2533
[POJ1458]: http://poj.org/problem?id=1458