X星人的基因
题目描述：
X星人的基因由A、B、C、D、E五种不同的结构组合而成。
如果两个性别不同的X星人的基因序列相似度大于50%，按照X星的法律他们是禁止结婚的，等于50%据说还是可以的。
那么基因的相似度怎么计算呢？分别从两个人身上取长度均为N的基因片段，如果它们的最长公共子序列（注意，最长公共子序列不需要连续）的长度为M，则相似度=M/N。是不是很简单呢？现在给你两段X星人的基因序列片段，请你判断他们是不是可以结婚？
输入描述：
单组输入。
每一组测试数据包含三行：
第1行数字N表示待比较基因序列片段的长度，N<=10^3。
第2行和第3行为两个长度为N的基因序列片段，中间以空格隔开。
输出描述：
先输出相似度，结果保留两位小数（四舍五入），然后输出判断结果（中间以空格隔开），如果可以输出“Yes”，如果不可以输出“NO”。
样例输入：
6
A B C D E E
A E D C B B
样例输出：
0.33 Yes
---------------------------------------------------------------------------------------------------
整体问题的核心代码还是LCS（最长公共子串）问题的动态规划策略，分别以二维数组保存结果（注释掉了）和优化后的一维数组保存结果为例。
注意因为输入的字符串内有空格，要编写个函数去掉空格不然很麻烦还要在LCS核心代码内做修改（因为不删空格每个配对的空格也算是LCS的一部分）。
题目很开放自己写main函数并且在其内用标准输入输出流，也是对C++基本功的考察吧哈哈，我这边以输入C风格字符串为例：
#include <iostream>
#include <string>
#include <stdlib.h>
#include <algorithm>
#include <iomanip>
using namespace std;////二维数组存储结果
//int longestCommonSubsequence(char* text1,char* text2)
//{
// int m = strlen(text1);
// int n = strlen(text2);
// int** dp = new int*[m+1];
// for (int i = 0; i < m+1;++i)
// {
// dp[i] = new int[n+1];
// }
// for (int i = 0; i < m+1; ++i)
// {
// for (int j = 0; j < n+1; ++j)
// {
// dp[i][j] = 0;
// }
// }
// for (int i = 1; i <= m; ++i)
// {
// for (int j = 1; j <= n; ++j)
// {
// if (text1[i] == text2[j])
// dp[i][j] = dp[i - 1][j - 1] + 1;
// else
// dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
// }
// }
// int lcs = dp[m][n];
// for (int i = 0; i < m + 1; ++i)
// {
// delete[] dp[i];
// }
// delete[] dp;
// return lcs;
//}//优化为滚动的一维数组存储结果
int longestCommonSubsequence(char* text1,char* text2)
{int m = strlen(text1);int n = strlen(text2);int* dp = new int[n+1];int last = 0;int temp = 0;fill(dp, dp + n + 1, 0);//dp数组初始化为0for (int i = 1; i <= m; ++i, last = 0){for (int j = 1; j <= m;++j){temp = dp[j];if (text1[i-1]==text2[j-1]){dp[j] = last + 1;}else{dp[j] = max(dp[j - 1], dp[j]);}last = temp;}}int lcs = dp[n];delete[] dp;return lcs;
}void deleteSpace(char* str)//删除空格函数（不开辟额外空间）
{int len = strlen(str);int k = 0;for (int i = 0; i < len;++i){if (str[i] != ' '){str[k] = str[i];k++;}}str[k] = '\0';//封闭字符串return;
}int main()
{int N;cin >> N;cin.get();//吃掉回车，没这个输入N之后直接结束了char* str1 = new char[N * 2];//这里考虑到想利用输入的N所以直接动态分配内存，当然你也可以直接在栈中创建一个容量足够大的数组char* str2 = new char[N * 2];cin.get(str1,N*2);cin.get();//同样吃掉回车cin.get(str2,N*2);//删除字符串内所有空格deleteSpace(str1);deleteSpace(str2);//调用LCS核心代码int lcs = longestCommonSubsequence(str1, str2);//这里要输出小数，做一下变化double fz = lcs;double fm = N;double similar = fz / fm;if (similar <= 0.5)//可以结婚{cout << setprecision(2) << fixed << similar <<" Yes"<< endl;//保留二位小数输出}else//不可以结婚{cout << setprecision(2) << fixed << similar << " No" << endl;//保留二位小数输出}//释放内存delete[] str1;delete[] str2;return 0;
}