BestCoder Round #87 1003 && hdu 5904(递推

时间:2022-08-05 19:31:43

LCIS

 
 Accepts: 109
 
 Submissions: 775
 Time Limit: 4000/2000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
问题描述
Alex有两个序列a_1,a_2,...,a_na1,a2,...,anb_1,b_2,...,b_mb1,b2,...,bm. 他想找到它们的最长公共递增子序列, 并且这个子序列的值是连续的(x,x+1,...,y-1,yx,x+1,...,y1,y).
输入描述
输入包含多组数据, 第一行包含一个整数TT表示测试数据组数. 对于每组数据:

第一行包含两个整数nnmm (1 \le n, m \le 100000)(1n,m100000)表示两个序列的长度. 第二行包含nn个整数: a_1, a_2, ..., a_na1,a2,...,an (1 \le a_i \le 10^6)(1ai106). 第三行包含mm个整数: b_1, b_2, ..., b_mb1,b2,...,bm (1 \le b_i \le 10^6)(1bi106).

输入最多有10001000组数据, 并且所有数据中nnmm的和不超过2 \times 10^62×106.
输出描述
对于每组数据, 输出一个整数表示长度.
输入样例
3
3 3
1 2 3
3 2 1
10 5
1 23 2 32 4 3 4 5 6 1
1 2 3 4 5
1 1
2
1
输出样例
1
5
0

思路:dp【a【i】】记录的是以a【i】为结尾的最长序列,有人说是dp,但是感觉并没有dp“做决策”的意义,因为数字是连续的,所以后面那个a[i] 的长度,一定等于前面a[i]-1的长度+1,如果 a[i]-1没出现过就0+1 = 1;如果这题问的是最长子序列,那就是dp了,因为要选择在哪一个后面才能使序列最长,也知道了,如果求两个数的公共最长子序列的做法,就是每一个序列都dp,然后遍历其中一个序列,找公共dp[a[i]]中的最大的,但是公共序列要是取最小的,(貌似也只能是连续的才能这么写。。)
有个坑点:就是用memset的话  如果最大数据是1e6会超时,1e5可以a,学了一招,用for循环清零
一般代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5;
int dp1[maxn],dp2[maxn],a[maxn],b[maxn];
int main()
{
    int t, n, m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
       memset(dp1,0,sizeof(dp1));
       memset(dp2,0,sizeof(dp2));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            dp1[a[i]] = max(dp1[a[i]-1] + 1,dp1[a[i]]);

        }
        for(int i = 1; i <= m; i++)
        {
            scanf("%d",&b[i]);
            dp2[b[i]] = max(dp2[b[i]-1] + 1,dp2[b[i]]);

        }
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            if(dp2[a[i]] != 0)
            ans =max(ans,min(dp1[a[i]],dp2[a[i]]));
        }
        printf("%d\n",ans);
    }
    return 0;

用for循环清零(别人代码)
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int dp1[1000001];
int dp2[1000001];
int a[100000], b[100000];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; ++i)
        {
            int a;
            scanf("%d", &a);
            ::a[i] = a;
            dp1[a] = max(dp1[a], dp1[a - 1] + 1);
        }
        for (int i = 0; i < m; ++i)
        {
            int b;
            scanf("%d", &b);
            ::b[i] = b;
            dp2[b] = max(dp2[b], dp2[b - 1] + 1);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans = max(ans, min(dp1[a[i]], dp2[a[i]]));
        printf("%d\n", ans);
        for (int i = 0; i < n; ++i)
            dp1[a[i]] = 0;
        for (int i = 0; i < m; ++i)
            dp2[b[i]] = 0;
    }
    return 0;
}

自己的递推:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5;
int dp1[maxn],dp2[maxn],a[maxn],b[maxn];
int main()
{
    int t, n, m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
       // for(int i = 0; i <= n; i++) dp1[i] = 0;
       // for(int i = 0; i <= m; i++) dp2[i] = 0;
       memset(dp1,0,sizeof(dp1));
       memset(dp2,0,sizeof(dp2));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            dp1[a[i]] = dp1[a[i]-1] + 1;

        }
        for(int i = 1; i <= m; i++)
        {
            scanf("%d",&b[i]);
            dp2[b[i]] = dp2[b[i]-1] + 1;

        }
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            if(dp2[a[i]] != 0)
            ans =max(ans,min(dp1[a[i]],dp2[a[i]]));
        }
        printf("%d\n",ans);
    }
    return 0;
}