poj1159题解

题解"/>

poj1159题解

//Memory 212K Time 985MS
#include <bits/stdc++.h>using namespace std;int getLength(string a, string b) {//存储记忆化结果int result[5010] = {0};//遍历a和b两个字符串的每个字符for (int i = 1; i <= a.size(); i++) {//暂时存储之前公共子串的长度(不包括当前遍历的b字符串的位置(即b字符串的当前字符))int temp = 0;for (int j = 1; j <= b.size(); j++) {//存储当前遍历到的位置(b字符串)的最大公共子串的长度int nowResult;//当两个字符串的最后两个字符一样,即result[j]的值可以等于d[j-1]+1即temp+1//若两个字符串的最后两个字符不一样,则可以分解为包括当前字符的最大公共子串的长度result[j]或不包括当前字符的最大公共子串的长度result[j-1]//取两者的较大值(因为题目求解的是最大公共子串)nowResult = a[i - 1] == b[j - 1] ? temp + 1 : max(result[j], result[j - 1]);temp = result[j];result[j] = nowResult;}}return result[b.size()];
}int main() {int strLength;//字符串长度string a, b;while (~scanf("%d", &strLength)) {getchar();//录入字符串agetline(cin, a);//填充字符串bfor (int i = a.size() - 1; i >= 0; i--)b.push_back(a[i]);//打印结果printf("%d\n", strLength - getLength(a, b));}return 0;
}

//简洁版
#include <bits/stdc++.h>using namespace std;int getLength(string a, string b) {int result[5010] = {0};for (int i = 1; i <= a.size(); i++) {int temp = 0;for (int j = 1; j <= b.size(); j++) {int nowResult;nowResult = a[i - 1] == b[j - 1] ? temp + 1 : max(result[j], result[j - 1]);temp = result[j];result[j] = nowResult;}}return result[b.size()];
}int main() {int strLength;string a, b;while (~scanf("%d", &strLength)) {getchar();getline(cin, a);for (int i = a.size() - 1; i >= 0; i--)b.push_back(a[i]);printf("%d\n", strLength - getLength(a, b));}return 0;
}

//Memory 49240K Time 954MS
//动态规划
#include <bits/stdc++.h>using namespace std;//存储记忆化结果
short result[5010][5010] = {0};//记忆化函数
int getLength(string a, string b) {//当b字符串为空时//即a和b的公共子串长度为0for (int i = 0; i <= a.size(); i++)result[i][0] = 0;//当a字符串为空时//即a和b的公共子串长度为0for (int i = 0; i <= b.size(); i++)result[0][i] = 0;//当a和b字符串都不为空时//记录两个字符串的每个长度的结果for (int i = 1; i <= a.size(); i++)for (int j = 1; j <= b.size(); j++)//外层条件a[i-1]==b[j-1]?//当两个字符串当前能够遍历到的字符//1.最后一个字符一样时,则可以将当前状态result[i][j]退化为result[i-1][j-1]+1//即假设当前状态,字符串a的长度为i-1,字符串b的长度为j-1,且两个字符串的最后一个字符不一样//那么a和b的最长公共子串的长度就存储在result[i-1][j-1]//此时在a和b的最后面都加个一样的字符,那么相应字符串的长度即都加1,即i和j//此时a和b的最长公共子串肯定会包括刚才新加的那个字符//即result[i][j]=result[i-1][j-1]+1//2.若a[i-1]!=b[j-1]//因为题目要求最长公共子序列,那么将result[i][j]就可以分解为result[i-1][j]和result[i][j-1]两种情况//当a和b的最后一个字符不相等时,即它们的公共子串肯定不会同时包括a和b的最后一个字符//即它们的公共子串可能包含a的最后一个字符或b的最后一个字符//所以result[i][j]就可以分解为result[i-1][j]和result[i][j-1]//取两者的较大值(问题求解最长公共子串)result[i][j] = a[i - 1] == b[j - 1] ? result[i - 1][j - 1] + 1 :result[i - 1][j] > result[i][j - 1] ? result[i - 1][j] : result[i][j - 1];return result[a.size()][b.size()];
}int main() {int strLength;//字符串长度string a, b;while (~scanf("%d", &strLength)) {getchar();//录入字符串agetline(cin, a);//填充字符串bfor (int i = a.size() - 1; i >= 0; i--)b.push_back(a[i]);//打印结果printf("%d\n", strLength - getLength(a, b));}return 0;
}

//简洁版
#include <bits/stdc++.h>using namespace std;short result[5010][5010] = {0};int getLength(string a, string b) {for (int i = 0; i <= a.size(); i++)result[i][0] = 0;for (int i = 0; i <= b.size(); i++)result[0][i] = 0;for (int i = 1; i <= a.size(); i++)for (int j = 1; j <= b.size(); j++)result[i][j] = a[i - 1] == b[j - 1] ? result[i - 1][j - 1] + 1 :result[i - 1][j] > result[i][j - 1] ? result[i - 1][j] : result[i][j - 1];return result[a.size()][b.size()];
}int main() {int strLength;string a, b;while (~scanf("%d", &strLength)) {getchar();getline(cin, a);for (int i = a.size() - 1; i >= 0; i--)b.push_back(a[i]);printf("%d\n", strLength - getLength(a, b));}return 0;
}