Common Subsequence
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 35240 | Accepted: 13986 |
Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1,
i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find
the length of the maximum-length common subsequence of X and Y.
Input
The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.
Output
For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
Sample Input
abcfbc abfcab programming contest abcd mnp
Sample Output
4 2 0
题目大意：直接求两个串的最长公共子序列。时间复杂度为O（n*m），n，m分别为两串的长度
看懂这个状态转移方程就可以了。
题目地址：Common Subsequence
AC代码：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char a[1005],b[1005];
int dp[1005][1005];
int main()
{
int i,j;
int len1,len2;
while(~scanf("%s%s",a+1,b+1))
{
len1=strlen(a+1);
len2=strlen(b+1);
for(i=0;i<=1000;i++)
{
dp[i][0]=0;
dp[0][i]=0;
}
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
{
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
/*for(i=1;i<=len1;i++)
{
for(j=1;j<=len2;j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}*/
cout<<dp[len1][len2]<<endl;
}
return 0;
}
/*
abcfbc abfcab
programming contest
abcd mnp
Ab3bd db3bA
ABCDE BBBBB
*/
Palindrome
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 49704 | Accepted: 17097 |
Description
A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order
to obtain a palindrome.
As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.
As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.
Input
Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from ‘A‘ to ‘Z‘, lowercase letters
from ‘a‘ to ‘z‘ and digits from ‘0‘ to ‘9‘. Uppercase and lowercase letters are to be considered distinct.
Output
Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.
Sample Input
5 Ab3bd
Sample Output
2
而且这个n是5000，5000*5000的数组当然开不下，所以需要用滚动数组来实现。
题目地址：Palindrome
AC代码：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char a[5005],b[5005];
int dp[2][5005]; //使用滚动数组
int main()
{
int len,i,j;
while(cin>>len)
{
scanf("%s",a+1);
//strcpy(b+1,a+1);
//strrev(b+1); //将a倒置赋值给b
for(i=1;i<=len;i++)
b[i]=a[len-i+1];
memset(dp,0,sizeof(dp));
for(i=1;i<=len;i++)
{
for(j=1;j<=len;j++)
{
if(a[i]==b[j])
dp[i%2][j]=dp[(i-1)%2][j-1]+1;
else
dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
}
}
int res;
res=len-dp[len%2][len];
cout<<res<<endl;
}
return 0;
}
/*
5
Ab3bd
*/