|
|
back to boardNo subject 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"; } Ответ Posted by aper 22 Aug 2018 12:25 Ошибка где-то тут: 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 |
|
|