本文主要是介绍POJ 1458 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题是求Longest Common Sequence，之前已经做过许多遍了。
| 1458 | Accepted | 364K | 16MS | C++ | 918B |
/*
ID: thestor1
LANG: C++
TASK: poj1458
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;int lcs(string &str1, string &str2)
{std::vector<std::vector<int> > dp(str1.size() + 1, std::vector<int>(str2.size() + 1, 0));for (int i = 1; i <= str1.size(); ++i){for (int j = 1; j <= str2.size(); ++j){if (str1[i - 1] == str2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;}else{dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[str1.size()][str2.size()];
}int main()
{string str1, str2;while (cin >> str1 >> str2){cout << lcs(str1, str2) << endl;}return 0;
}这篇关于POJ 1458 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
