|
|
back to boardPlease tell me how to solve it.... I have got WA 23, but I know that my algo will have TLE... What is the right algo??? Re: Please tell me how to solve it.... Accepted!!!! BFS - very good thing!!!! Re: Please tell me how to solve it.... Posted by Игор 10 Feb 2020 00:19 #include <iostream> #include <algorithm> #include <string> unsigned counter = 0; void printPalindroms(unsigned short *splitIndex, unsigned short i, const std::string& str){ if(splitIndex[i] == 0){ std::cout<<str.substr(0, i+1)<<" "; }else{ printPalindroms(splitIndex, splitIndex[i]-1, str); std::cout<<str.substr(splitIndex[i], i + 1 - splitIndex[i])<<" "; } } int main() { std::string strr; std::cin>>strr; const char* str = strr.data(); unsigned length = strr.size(); unsigned arrSize = (length*length + length)/2; bool *pArrData = new bool[arrSize]; bool **pArr = new bool*[length]; unsigned short *splitWeights = new unsigned short [length]; unsigned short *splitIndex = new unsigned short[length]; std::fill(pArrData, pArrData + arrSize, false); std::fill(splitWeights, splitWeights + length, length +2); std::fill(splitIndex, splitIndex + length, 0);
unsigned offset = 0; for(unsigned i = 0; i<length; ++i){ pArr[i] = pArrData + offset; offset += length - i; } // init the first row std::fill(pArr[0], pArr[0] + length, true); //init the second row for(unsigned i = 0; i<length - 1; ++i){ if(str[i] == str[i+1]){ pArr[1][i] = true; } } for(unsigned i = 2; i < length; ++i){ for(unsigned j = 0; j< length - i; ++j){ if(pArr[i-2][j+1] && str[j] == str[j+i]){ pArr[i][j] = true; } } } for(unsigned i = 0; i < length; ++i){ if(pArr[i][0] == true){ splitWeights[i] = 0; splitIndex[i] = 0; }else{ for(unsigned j = 1; j <= i; ++j){ if(pArr[i-j][j]){ unsigned short temp = splitWeights[j-1] + 1; if(temp < splitWeights[i]){ splitWeights[i] = temp; splitIndex[i] = j; } } } } } std::cout<<splitWeights[length -1] + 1<<std::endl; printPalindroms(splitIndex, length - 1, strr); delete[] splitIndex; delete[] splitWeights; delete[] pArr; delete[] pArrData;
return 0; } |
|
|