Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <cstring>
- using namespace std;
- ifstream fin("cuvant2.in");
- ofstream fout("cuvant2.out");
- int n, nr, maxx, a[270][270];
- char s[270];
- void tipar(int st, int dr, int &nr, int &maxx)
- {
- if(a[st][dr]==1)
- {
- int lung=dr-st+1;
- if(lung>=maxx)
- maxx=lung;
- nr++;
- /*for(int i=st; i<=dr; i++)
- {
- fout<<s[i];
- }
- fout<<'\n';*/
- }
- else
- {
- int k=st;
- while(a[st][k]+a[k+1][dr] != a[st][dr])
- {
- k++;
- }
- int lung=k-st+1;
- if(lung>=maxx)
- maxx=lung;
- nr++;
- /*for(int i=st; i<=k; i++)
- {
- fout<<s[i];
- }
- fout<<'\n';*/
- tipar(k+1, dr, nr, maxx);
- }
- }
- int main()
- {
- int i,j,k,x;
- fin>>s;
- n=strlen(s);
- for(i=0; i<n-1; i++)
- {
- a[i][i]=1;
- if(s[i]==s[i+1])
- a[i][i+1]=1;
- else
- a[i][i+1]=2;
- }
- a[n-1][n-1]=1;
- for(j=2; j<n; j++)
- {
- for(i=j-2; i>=0; i--)
- {
- if(s[i]==s[j] && a[i+1][j-1]==1)
- a[i][j]=1;
- else
- {
- x=2000000000;
- for(k=j-1; k>=i; k--)
- {
- if(a[i][k]+a[k+1][j]<x)
- {
- x=a[i][k]+a[k+1][j];
- }
- a[i][j]=x;
- }
- }
- }
- }
- /*for(i=0; i<n; i++)
- {
- for(j=0; j<n; j++)
- {
- fout<<a[i][j]<<" ";
- }
- fout<<'\n';
- }*/
- nr=0; maxx=-1;
- tipar(0, n-1, nr, maxx);
- fout<<nr<<" "<<maxx;
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement