首页 > ACM题库 > HDU-杭电 > HDU 1423 Greatest Common Increasing Subsequence-动态规划-[解题报告] C++
2013
12-10

HDU 1423 Greatest Common Increasing Subsequence-动态规划-[解题报告] C++

Greatest Common Increasing Subsequence

问题描述 :

This is a problem from ZOJ 2432.To make it easyer,you just need output the length of the subsequence.

输入:

Each sequence is described with M – its length (1 <= M <= 500) and M integer numbers Ai (-2^31 <= Ai < 2^31) – the sequence itself.

输出:

output print L – the length of the greatest common increasing subsequence of both sequences.

样例输入:

1

5
1 4 2 5 -12
4
-12 1 2 4

样例输出:

2

题目听起来就很复杂的样子。

对于每一个内循环,我们关心的是b[j]和a[i]的比较情况,如果b[j]<a[i],那么我们可以确定,在我们最终要找到的子序列里,如果b[j]也在其中,那么它一定是在b[j*](b[j*]==a[i])的前面,也就是说让k等于j,f[j*]可以通过f[j]加上某个值确定,加上的值就是f[j*]和f[j]中符合条件的解的值的数量。所以,对于f[j]>f[k],我们直接让k=j,这样当j循环走到j*的时候,f[j]就等于f[k]+1。

不过,这个PE算是怎么回事儿?!

#include<stdio.h>
#include<string.h>
#define N 505
int main()
{
    int n,m;
    int a[N],b[N],f[N];
    int i,j,k;
    int ans;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&m);
        for(i=1;i<=m;i++)
            scanf("%d",&a[i]);
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&b[i]);
        memset(f,0,sizeof(f));
        for(i=1;i<=m;i++)
        {
            k=0;
            for(j=1;j<=n;j++)
            {
                if(b[j]<a[i]&&f[j]>f[k])
                    k=j;
                if(b[j]==a[i])
                    f[j]=f[k]+1;
            }
        }
        ans=0;
        for(i=0;i<=n;i++)
        {
            if(ans<f[i])
                ans=f[i];
        }
        printf("%d\n",ans);
        if(T!=0)
            printf("\n");
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/zizaimengzhongyue/article/details/8931810


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])