bonnon Answer b onno n Edited by author 27.10.2022 10:18 Edited by author 27.10.2022 10:19 might it is very complicated but i use hash and dp to solve this problem I had MLE on test 33. I just changed int to short and 1,0 to bool Sorry if this is too obvious Edited by author 22.11.2020 16:48 consider follow string: ABZZBBBZZA. 2 polindroms: ZZBBBZZ and ABA - correctly for this problem? i think answer is 3 polindroms: AB ZZBBBZZ A I thin its 4 palindromes A B ZZBBBZZ A Смотрю с любовью на свои более 10-летней давности попытки решать задачи. Спасибо, ACM.Timus! I have got WA 23, but I know that my algo will have TLE... What is the right algo??? Accepted!!!! BFS - very good thing!!!! #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; } I am getting wrong answer.Please give me some test case. My solution: #include<iostream> #include<string.h> #include<string> #include<stdlib.h> #include<stdio.h> #include<vector> #include<algorithm> using namespace std; string line; bool check(int s,int e) { string temp; for(int i=s; i<=e; i++) temp.push_back(line[i]); string temp2=temp; reverse(temp.begin(),temp.end()); if(temp==temp2) return true; return false; } int dp[4005][4005]; int palindrome(int s,int e) { if(s>=e) return 0; if(dp[s][e]!=-1) return dp[s][e]; int ans=(1<<30); for(int i=s; i<e; i++) if(check(s,i)) { ans=min(ans,1+palindrome(i+1,e)); } return dp[s][e]=ans; } vector<string>anss; void print(int s,int e) { int b=palindrome(s,e); if(b==1) { string temp; for(int i=s; i<e; i++) temp.push_back(line[i]); anss.push_back(temp); return; } for(int i=s; i<e; i++) if(b==1+palindrome(i+1,e)) { string temp; for(int j=s;j<=i;j++) temp.push_back(line[j]); anss.push_back(temp); print(i+1,e); break; } } int main() { cin>>line; int len; len=line.size(); anss.clear(); memset(dp,-1,sizeof dp); cout<<palindrome(0,len)<<endl; print(0,len); len=anss.size(); for(int i=0;i<len-1;i++) cout<<anss[i]<<" "; cout<<anss[len-1]<<"\n"; } Ошибка где-то тут: string line; bool check(int s,int e) { string temp; for(int i=s; i<=e; i++) temp.push_back(line[i]); string temp2=temp; reverse(temp.begin(),temp.end()); if(temp==temp2) return true; return false; } int dp[4005][4005]; int palindrome(int s,int e) { if(s>=e) return 0; if(dp[s][e]!=-1) return dp[s][e]; int ans=(1<<30); for(int i=s; i<e; i++) if(check(s,i)) { ans=min(ans,1+palindrome(i+1,e)); } return dp[s][e]=ans; } vector<string>anss; void print(int s,int e) { int b=palindrome(s,e); if(b==1) { string temp; for(int i=s; i<e; i++) temp.push_back(line[i]); anss.push_back(temp); return; } for(int i=s; i<e; i++) if(b==1+palindrome(i+1,e)) { string temp; for(int j=s;j<=i;j++) temp.push_back(line[j]); anss.push_back(temp); print(i+1,e); break; } } int main() { cin>>line; int len; len=line.size(); anss.clear(); memset(dp,-1,sizeof dp); cout<<palindrome(0,len)<<endl; print(0,len); len=anss.size(); for(int i=0;i<len-1;i++) cout<<anss[i]<<" "; cout<<anss[len-1]<<"\n"; } Edited by author 22.08.2018 12:26 Edited by author 22.08.2018 12:26 Try this abacabadabacab. The problem is in hash. Answer is : a bacabadabacab Edited by author 15.08.2018 21:18 It is something unique I have had WA20, WA23, TLE32, MLE56 But never WA42 nvm accepted Edited by author 05.02.2017 04:33 Can anyone give me some test cases because I really don't know where my program is wrong ? Nevermind, this test case helped me find my mistake: "ababbaa" Me too. Thanks nice test. pls help Edited by author 24.02.2016 16:20 try this: aaaba is 2 aa aba not 3 aaa b a WA #7 can anyone help plz? using simple dp you are probably considering to get rid of palindromes as early as possible for example, consider the case "aabba" if you say it is 3 palindromes: "aa", "bb", and "a", then you are wrong, since it can be "a" and "abba" Build a data-structure which allows O(1) test that s[from..to] is a palindrome. The structure is a 2 x s.size() array: even/odd length times possible center point. typedef vector<int> V; string s(4001, ' '); int n; V mpl[2]; // maximum palindrome length around i (even and odd lengths) inline bool is_polindrome(int from, int to){ assert(0 <= from and from < to and to <= n); int eo = (to - from) % 2, c = (from + to) / 2; return mpl[eo][c] >= c - from; } One can think like that: Let a(k) be the amount of palindromes in [0,k]. Then we have recursion: a(k)=MIN{ 1 if [0,k] is pm , MIN (from i = 0 to k -1) OF a(i) + 1 if [i,k] is pm} { 0 else a(i) + k-i else } I consider ASK to be absolutely right concerning data structure He proposed.
Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even). Time complexity for this step is O(n^2) maybe it will be useful (or at least interesting) for somebody. at first i tried to make simple DP with O(n^3). i tried in java (and i received TLE in 32th test). after that i tried to realize greed algorithm and understood that this idea is wrong (simple antigreed test is: "abzzbbbzza") aand finally i've made O(n^2) DP. little hint: try to precalc d[l][r]: d[l][r] = true, s[l..r] - palindrom d[l][r] = false, s[l..r] - not palindrom whats the ans for 'abzzbbbzza'? i didn't get it how it will become n^2 because for l=1 to l=n is one loop and for r=l to r=n is inside loop and for checking it is palindrome is another loop so i don't get how it will be n^2 can you please explain me i am very confused here please help me Can you tell me why I always WA #1? Beacause I have tested all those samples in the board, and I pass them all... OK...I have got it...in Ural...in C...You must write like boolflag == 1...You can not write like boolflag,which works in my computer... aaaabaaa correct answer is 2 a aaabaaa your example is very good ! Stuck at test case #12 Per reply in 2008, someone suggested testing with axayaaxa I don't know whether this is the real #12. But I tried anyway. My program answers a x aya axa And another possible answer is axa y a axa Both with 4 palindromes. Question says output any is correct. Suggestion? Thanks in advance! I spotted a bug. Will fix it first and try again. Edited by author 08.09.2011 17:57 Give me your code ! I also WA 19,but I find write wrong dp[i]>dp[j-1]+1 to dp[i]>dp[j]^…… I test my code at my computer,I got a test which is filled by period string "abcde" and its length is 4000,and my program run only 0.25s. My computer is: Memory:3GB System:Windows XP CPU:1.66GHZ But I got tle at #32...Why??? Here is my code. var i,j,xx,ox,t,l:longint; s:ansistring; f,x:array [1..4010] of longint; o:array [0..4010] of boolean; function pdhw(l,r:longint):boolean; var i:longint; begin if l=r then exit(true); for i:=l to (l+r)>>1+1 do if s[i]<>s[r+l-i] then exit(false); exit(true); end; begin readln(s); l:=length(s); for i:=1 to l do begin f[i]:=maxlongint; if pdhw(1,i) then f[i]:=0 else for j:=1 to i-1 do if (f[i]>f[j]+1)and(pdhw(j+1,i)) then begin f[i]:=f[j]+1; x[i]:=j; end; end; writeln(f[l]+1); xx:=l; repeat ox:=xx; xx:=x[xx]; if ox=l then o[xx+1]:=true else o[xx+1]:=true; until xx=0; o[1]:=false; for i:=1 to length(s) do if o[i] then write(' ',s[i]) else write(s[i]); end. |
|