Advertisement
Guest User

Cod cuvant2

a guest
Dec 8th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstring>
  4. using namespace std;
  5. ifstream fin("cuvant2.in");
  6. ofstream fout("cuvant2.out");
  7. int n, nr, maxx, a[270][270];
  8. char s[270];
  9.  
  10. void tipar(int st, int dr, int &nr, int &maxx)
  11. {
  12. if(a[st][dr]==1)
  13. {
  14. int lung=dr-st+1;
  15. if(lung>=maxx)
  16. maxx=lung;
  17. nr++;
  18. /*for(int i=st; i<=dr; i++)
  19. {
  20. fout<<s[i];
  21. }
  22. fout<<'\n';*/
  23. }
  24. else
  25. {
  26. int k=st;
  27. while(a[st][k]+a[k+1][dr] != a[st][dr])
  28. {
  29. k++;
  30. }
  31. int lung=k-st+1;
  32. if(lung>=maxx)
  33. maxx=lung;
  34. nr++;
  35. /*for(int i=st; i<=k; i++)
  36. {
  37. fout<<s[i];
  38. }
  39. fout<<'\n';*/
  40. tipar(k+1, dr, nr, maxx);
  41. }
  42. }
  43.  
  44. int main()
  45. {
  46. int i,j,k,x;
  47. fin>>s;
  48. n=strlen(s);
  49. for(i=0; i<n-1; i++)
  50. {
  51. a[i][i]=1;
  52. if(s[i]==s[i+1])
  53. a[i][i+1]=1;
  54. else
  55. a[i][i+1]=2;
  56. }
  57. a[n-1][n-1]=1;
  58. for(j=2; j<n; j++)
  59. {
  60. for(i=j-2; i>=0; i--)
  61. {
  62. if(s[i]==s[j] && a[i+1][j-1]==1)
  63. a[i][j]=1;
  64. else
  65. {
  66. x=2000000000;
  67. for(k=j-1; k>=i; k--)
  68. {
  69. if(a[i][k]+a[k+1][j]<x)
  70. {
  71. x=a[i][k]+a[k+1][j];
  72. }
  73. a[i][j]=x;
  74. }
  75. }
  76. }
  77. }
  78. /*for(i=0; i<n; i++)
  79. {
  80. for(j=0; j<n; j++)
  81. {
  82. fout<<a[i][j]<<" ";
  83. }
  84. fout<<'\n';
  85. }*/
  86. nr=0; maxx=-1;
  87. tipar(0, n-1, nr, maxx);
  88. fout<<nr<<" "<<maxx;
  89. fin.close();
  90. fout.close();
  91. return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement