HDU 1423 LICS 模板-白红宇

HDU 1423 LICS 模板

阅读量：4623 次

发布时间：2019-06-09

本文共 1548 字，大约阅读时间需要 5 分钟。

4、LICS、O（lena * lenb）

设dp[i][j]表示a[]的前i项，以b[]的第j项结尾时，能匹配的最大值。

①、不匹配a[i]这个数，则是dp[i][j] = dp[i – 1][j];

②、匹配a[i]这个数，则需要a[i] == b[j] && b[j] > b[k] 推出 dp[i][j] = max(dp[i – 1][k]) + 1，

这样复杂度需要O(n³)，注意到，求解dp的时候，是从dp[i][1….lenb]这样的顺序求解，而且，需要a[i] == b[j]才能算做贡献，因为要LCS嘛！那么可以记录dp[i][1…j – 1]的信息，以a[i]作为基准（因为a[i] == b[j]才能算出贡献，以那个作为基准没所谓），找出前j - 1个数中，满足LIS并且最大的那个，O(1)更新即可。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    const int maxn = 500 + 20;int dp[maxn][maxn];int a[maxn], b[maxn];void work() { int lena, lenb; cin >> lena; for (int i = 1; i <= lena; ++i) { cin >> a[i]; } cin >> lenb; for (int i = 1; i <= lenb; ++i) { cin >> b[i]; } memset(dp, 0, sizeof dp); for (int i = 1; i <= lena; ++i) { for (int j = 1, cnt = 0; j <= lenb; ++j) { dp[i][j] = dp[i - 1][j]; //不要当前这个a[i] if (a[i] > b[j]) { //形成LIS cnt = max(cnt, dp[i - 1][j]); } if (a[i] == b[j]) { //形成LCS dp[i][j] = cnt + 1; } } } int ans = 0; for (int i = 1; i <= lenb; ++i) ans = max(ans, dp[lena][i]); cout << ans << endl;}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif int t; cin >> t; while (t--) { work(); if (t) printf("\n"); } return 0;}

View Code

转载于:https://www.cnblogs.com/liuweimingcprogram/p/6523607.html

你可能感兴趣的文章