首页 > ACM题库 > HDU-杭电 > Hdu 1758 Two Brothers[解题报告] C++
2013
12-23

Hdu 1758 Two Brothers[解题报告] C++

Two Brothers

问题描述 :

Though Yueyue and Lele are brothers , they are very different.
For example, Yueyue is very hard in study, especially in writing compositions. To make the composition looks nice , he will not use the same word twice. While Lele is very lazy, and he sometimes copys his brother’s homework.Last week, their teacher asked them to write a composition named “My Mother”, they handed the same composition. The teacher was very angry , but Lele just answered “We have the same mother , why should our compositions be different ?”

Now,the teacher is asking Yueyue and Lele to write the compositions again, and he wants to calculate the length of longest common subsequence of words occuring in the two compositions. Can you help him ?

输入:

There will be many test cases in the problem.Please process to the end of file.
Each case contains two lines.
The first line means Yueyue’s composition and the second line means Lele’s composition.
Each composition will contains no more than 10^4 words . And each word will contains less than 40 characters.Each character will only be in a~z or A~Z.
Two words will be separated by a blank.To make the problem easier, there will be a “#” at the end of each composition.

输出:

For each case , output a integer in a line represents the length of longest common subsequence of words occuring in the their compositions.

样例输入:

aa bb cc #
aa cc bb #

样例输出:

2
Hint

Huge input,the C function scanf() will work better than cin


我们先开始了解LIS(Longest Increasing Subsequence)最长上升(不下降)子序列 。

同样有两种算法复杂度为O(n*logn)和O(n^2);

这里给出O(n*logn)的算法:

int LIS(int str[],int len)
{
    int max,left,right,i,mid;
    lis[1] = str[0];
    max = 1;
    for(i=1; i<len; i++)
    {
        if(str[i] > lis[max])
        {
            lis[++max] = str[i];
        }
        else
        {
            left = 1;
            right = max;
            while(left <= right)
            {
                mid = (left+right)/2;
                if(str[i] > lis[mid])
                    left = mid + 1;
                else if(str[i] < lis[mid])
                    right = mid - 1;
                else
                    break;
            }
            lis[left] = str[i];
        }
    }
    return max;
}

 

另一种写法(加深理解)

#include <iostream>
using namespace std;

#define  MAX_INPUT_NUM 10000
int limit[MAX_INPUT_NUM];

int main()
{
    int inputNum;
    int curNum;
    int tempBegin;
    int tempEnd;
    int tempMiddle;
    int len;
    
    while(cin>>inputNum){
        len=0;//the count
        for(int i=0;i<inputNum;i++){
            cin>>curNum;

            tempEnd=len;
            tempBegin=1;
            tempMiddle=0;

            while(tempBegin<=tempEnd){
                tempMiddle=(tempBegin+tempEnd)>>1;
                limit[tempMiddle] >=curNum ? tempEnd=tempMiddle-1 : tempBegin=tempMiddle+1;
            }
            limit[tempBegin]=curNum;//first position whose value >=curNum ,if no existed ,is end+1
            tempBegin >len ? len++ :NULL;
    
        }//end for ..
        cout<<len<<endl;
    }//end while

    return 0;
}

 


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。