浙江财经大学
信工学院ACM集训队

SCU 2796 Letter Deletion

本文由 Ocrosoft 于 2016-08-03 15:24:08 发表

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

You are given two words (each word consists of upper-case English letters). 
Try to delete some letters from each word so that the resulting words are equal. 
What is the maximum possible length of the resulting word?

Input

There will be no more than 10 test cases. 
Each test case consists of a single line, contaning the two words separated by a single space. The length of each of these words is between 1 and 200.

Output

For each test case output the maximum length of a resulting word (the length of the longest word that can be created from both words by removing some letters). 
If the two words have no letters in common, output 0.

Sample Input

AAABBB ABABAB
AXYAAZ CCCXCCCYCCCZCC
ABCDE EDCBA

Sample Output

4
3
1

Solution

就是最长公共子序列。
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 200+10
using namespace std;
int main()
{
    string a,b;
    while(cin>>a>>b)
    {
        int la=a.size(),lb=b.size();
        int ans[MAXN][MAXN];
        for(int i=1; i<=la; i++)
        {
            for(int j=1; j<=lb; j++)
            {
                if(a[i-1]==b[j-1])
                    ans[i][j]=ans[i-1][j-1]+1;
                else if(ans[i-1][j]>=ans[i][j-1])
                    ans[i][j]=ans[i-1][j];
                else
                    ans[i][j]=ans[i][j-1];
            }
        }
        printf("%d\n",ans[la][lb]);
    }
    return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » SCU 2796 Letter Deletion

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址