这一题有点烦
我一开始的思路是,回文序列么,就是正序字符串和逆序字符串中相同的那一串
于是乎,就转化成求最长公共子字符串,于是用动态规划,O(N^2)的时间复杂度和空间复杂度
首先是内存超了,于是换成O(n)空间复杂度的实现方式,即只记录上一状态就可以
接着到最后一个测试程序的时候,时间也超了
无奈,想不出其他思路的情况下,看了NOCOW的解题,O(n)的动态规划
思路是这样的:
写道
begin
if cha[i]=cha[i-1] then f[i]:=i-1;
if cha[i]=cha[f[i-1]-1] then f[i]:=f[i-1]-1;
end;
if cha[i]=cha[i-1] then f[i]:=i-1;
if cha[i]=cha[f[i-1]-1] then f[i]:=f[i-1]-1;
end;
以下是代码,注释部分是我一开始的思路:
/* ID: bbsunch2 PROG: calfflac LANG: C++ */ #include <iostream> #include <fstream> #include <string> #include <vector> #include <stdlib.h> #include <algorithm> using namespace std; int main() { ofstream fout ("calfflac.out"); ifstream fin ("calfflac.in"); string input = ""; while(fin.good() && !fin.eof()) { string line; getline(fin,line,'\n'); input = input + line + "\n"; } //cout << input << endl; //建立字符串中的字母和原始字符串位置对应关系 int charIndicator = -1; vector<int> correspondingPosition; string letterString = ""; for(int i = 0; i < input.size(); i++) { char single = input[i]; if(single >= 'A' && single <= 'Z') { charIndicator++; letterString += single; correspondingPosition.push_back(charIndicator); }else if(single >= 'a' && single <='z') { single = single - 32; charIndicator++; letterString += single; correspondingPosition.push_back(charIndicator); }else { charIndicator++; } } vector<int> f; f.push_back(0); for(int i = 1; i < letterString.size(); i++) { if(letterString[i] == letterString[f[i-1]]) { f.push_back(i-1); if(letterString[i] == letterString[f[i-1]-1]) { f[i] = (f[i-1]-1); } }else if(f[i-1] - 1 >=0) { if(letterString[i] == letterString[f[i-1]-1]) { f.push_back(f[i-1]-1); }else { f.push_back(i); } }else { f.push_back(i); } } int maxI = 0; int maxStep = 0; for(int i = 1; i < letterString.size(); i++) { if(maxStep < i-f[i]+1) { maxStep = i - f[i]+1; maxI = i; } } /*string reverseLetterString = ""; for(int i = letterString.size()-1; i >= 0; i--) { reverseLetterString += letterString[i]; } //vector<vector<int> > matrix; int maxI = 0; int maxStep = 0; vector<int> line1; vector<int> line2; for(int i = 0; i < letterString.size(); i++) { line1.push_back(0); line2.push_back(0); } for(int i = 0; i < letterString.size(); i++) { vector<int> lineInMatrix; for(int k = 0; k < letterString.size(); k++) { lineInMatrix.push_back(0); } matrix.push_back(lineInMatrix); } for(int k = 0; k < reverseLetterString.size(); k++) { for(int i = 0; i < letterString.size(); i++) { line2[i] = 0; if(letterString[i] == reverseLetterString[k]) { if(i == 0 || k == 0) { line2[i] = 1; }else { line2[i] = line1[i-1] + 1; } if(maxStep <= line2[i]) { maxStep = line2[i]; maxI = i; } } } for(int index = 0; index < letterString.size(); index++) { line1[index] = line2[index]; } }*/ fout << maxStep << endl; int startLetterPosition = maxI - maxStep + 1; int startPosition = correspondingPosition[startLetterPosition]; int endPosition = correspondingPosition[maxI]; string sub = input.substr(startPosition, endPosition - startPosition + 1); fout << sub << endl; return 0; }
相关推荐
USACO所有题目的题解 NOCOW整理版
Usaco中第一章中的一道题,挺有意思的。我的程序中间用到了折半查找,牺牲空间求效率
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
USACO月赛题解1
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
丰富的USACO1.1--2.3.4的所有题解
非常详细的题解,个人觉得很好,帮助非常大。nocow关闭后不太好找资源了。
非常详细的题解,比较全的,个人觉得刷题者可以入手,帮助非常大。
非常详细的题解,比较全的,个人觉得刷题者可以入手,帮助非常大。
非常详细的题解,个人觉得比较全的,刷题者可以入手,帮助会非常大。
我的USACO题解和程序
USACO题解(NOCOW整理版).doc
usaco全部题解。 网址:blog.csdn.net/jiangshibiao
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写
里面有usaco前几节的程序和代码,欢迎使用,希望对你有所帮主。
usaco的某道题的题解
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
USACO(即美国高中生的编程竞赛网站)中的 pprime 题的题解
数据结构机考所参考的USACO网站所有题目的解题思路,资源比较稀有!