HDU 5904 - LCIS (BestCoder Round #87)

HDU 5904 - LCIS [ DP ] BestCoder Round #87

题意：

给定两个序列，求它们的最长公共递增子序列的长度, 并且这个子序列的值是连续的

分析：

状态转移方程式： dp[a[i]] = max(dp[a[i]], dp[a[i]-1] + 1);

发现其实可以简化为 dp[a[i]] = dp[a[i]-1] + 1；因为计算过程中dp[a[i]]不会降低

对两个序列都求一遍，然后取两者最小值的最大值

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 using namespace std;

 const int MAXM = ;

 const int MAXN = ;

 int t, n, m;

 int a[MAXN], b[MAXN];

 int dp1[MAXM], dp2[MAXM];

 int main()

 {

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d%d", &n, &m);

         memset(dp1, , sizeof(dp1));

         memset(dp2, , sizeof(dp2));

         int top = ;

         for (int i = ; i <= n; i++)

         {

             scanf("%d", &a[i]);

             dp1[a[i]] = dp1[a[i]-] + ;

             top = max(top, a[i]);

         }

         for (int i = ; i <= m; i++)

         {

             scanf("%d", &b[i]);

             dp2[b[i]] = dp2[b[i]-] + ;

             top = max(top, b[i]);

         }

         int ans = ;

         for (int i = ; i <= top; i++) ans = max(ans, min(dp1[i], dp2[i]));

         printf("%d\n", ans);

     }

 }

巴特西

HDU 5904 - LCIS (BestCoder Round #87)

最新文章

热门文章