1730 - 顺序对齐
时间限制 : 1 秒
内存限制 : 128 MB
考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是AADDEFGGHC和ADCDEGH。
AAD_DEFGGHC
ADCDE__GH_
每一个数值匹配的位置值2分，一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数，在上述给定的例子中，6个位置(A,D,D,E,G,H)匹配，三段空格，所以得分2*6+(-1)*3=9，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。
请你写个程序找出最佳右对齐方案。
题目输入
每笔测资包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。
题目输出
每笔测资输出一行，为最佳对齐得分。
输入/输出样例
输入格式
AADDEFGGHC ADCDEGH
输出格式
9
C++解答
#include<iostream> #include<string> #include<algorithm> #include<cstring> using namespace std; const int N(55); int f[N][N]={0}; int main() { string s1,s2; int i,j,len1,len2; while (cin>>s1>>s2) { memset(f,0,sizeof(f)); len1=s1.size(); len2=s2.size(); for (i=1;i<=len1;i++) for (int j=1;j<=len2;j++) { f[i][j]=f[i-1][j-1]+(s1[i-1]==s2[j-1]?2:0); for (int k=1;k<i;k++) f[i][j]=max(f[i][j],f[k][j]-1); for (int k=1;k<j;k++) f[i][j]=max(f[i][j],f[i][k]-1); } cout<<f[len1][len2]<<endl; } return 0; }