题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1346

Dynamic programming

需要注意的是input里可能含有空行,一行空行也是一个string,所以如果用scanf("%s", string)是不能把空行存进string变量里的。需要用gets或者getline来处理input。

可惜的是我目前对于gets,getline的用法还没有很熟悉,之后会关于这方面的区别做解释。又或者有大神可以帮忙讲解一下,感恩

代码如下:

 #include <iostream>
#include <math.h>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <cmath>
#define SCF(a) scanf("%d", &a)
#define IN(a) cin>>a
#define FOR(i, a, b) for(int i=a;i<b;i++)
typedef long long Int;
using namespace std; int main()
{
char str1[];
char str2[];
int len1, len2;
while (cin.getline(str1, ))
{
cin.getline(str2, );
for (len1 = ; str1[len1] != '\0'; len1++);
for (len2 = ; str2[len2] != '\0'; len2++);
int** match;
match = new int*[len1+];
FOR(i, , len1 + )
match[i] = new int[len2 + ];
FOR(i, , len1 + )
match[i][] = ;
FOR(i, , len2 + )
match[][i] = ; FOR(i, , len1 + )
{
FOR(j, , len2 + )
{
if (str1[i - ] == str2[j - ])
match[i][j] = match[i - ][j - ] + ;
else
{
match[i][j] = max(match[i - ][j], match[i][j - ]);
}
}
} printf("%d\n", match[len1][len2]);
FOR(i, , len1 + )
delete[] match[i];
delete[] match;
}
return ;
}
05-11 13:48