fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //#include <boost/multiprecision/cpp_int.hpp>
  4. //using namespace boost::multiprecision;
  5. #define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  6. #pragma GCC optimize "trapv"
  7. #define _GLIBCXX_DEBUG
  8. #define ll long long int
  9. #define ld long double
  10. #define ull unsigned long long int  // ranges from (0 - twice of long long int)
  11. #define rep(i,a,n) for (ll i=a;i<n;i++)
  12. #define per(i,a,n) for (ll i=n-1;i>=a;i--)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define vll vector<ll>
  16. #define mod 1000000007LL
  17. #define llpair pair<ll,ll>
  18. #define INF 1000000000000000000ll
  19. #define np next_permutation
  20. #define PI acos(-1)
  21. #define deb(x) cout<<#x<<" "<<x<<endl;
  22. #define rotate_left(vec,amt) rotate(vec.begin(),vec.begin()+amt,vec.end());
  23. #define rotate_right(vec,amt) rotate(vec.begin(),vec.begin()+vec.size()-amt,vec.end());
  24. #define all(x) x.begin(),x.end()
  25. #define sortall(x) sort(all(x))
  26. #define clr0(x) memset(x,0,sizeof(x))
  27. #define clr1(x) memset(x,-1,sizeof(x))
  28.  
  29.  
  30. ll static dp[1001][1001]; //create a dp table according to constraints.
  31. bool static pal[1001][1001]; // create table to answer i to j is palindrome or not;
  32. // step 1
  33.  
  34.  
  35. ll palindrome_partition(string s,ll i, ll j)
  36. {
  37.  
  38. 	if(i>j) // means the gives strings having ends i and j are empty    // first invalid condition.
  39. 	return 0;  // it means we no more cuts required. 
  40.  
  41. 	if(dp[i][j]!=-1) return dp[i][j]; // step 3 
  42.  
  43. 	//if(is_palindrome(s,i,j))
  44. 	//return 0;  // already is palidrome so no more cost/cuts is required
  45. 						  // or we can say no of cuts required is 0.
  46.  
  47. 	if(pal[i][j]) return 0;   // if already a palindromic subsequence then return cost to be 0
  48.  
  49. 	ll mina=INT_MAX;
  50. 	for(ll k=i;k<=j-1;k++)
  51. 	{
  52. 		ll tempans=palindrome_partition(s,i,k) +
  53. 		palindrome_partition(s,k+1,j) + 1;// here 1 is for doing current cost to break i,j to (i to k) and (k+1 to j)
  54.  
  55. 		mina=min(mina,tempans);
  56. 	}
  57.  
  58. 	return (dp[i][j]=mina);
  59. }
  60.  
  61. int main() {
  62.     auto start = chrono::high_resolution_clock::now();
  63.     fio;
  64.     ll t=1; 
  65.     cin>>t; 
  66.     while(t--)
  67.     {
  68. 		//ll n; cin>>n;
  69. 		string s; cin>>s;
  70. 		clr1(dp);  // step 2, make dp table with -1;
  71. 		clr0(pal);
  72. 		ll n=s.length();
  73.  
  74.  
  75. 		// code for finding palindromic substring
  76. 		// code start
  77. 		for(int i=0;i<n;i++)
  78. 		pal[i][i]=1;
  79.  
  80. 		// explicitly for 2 length
  81. 		for(int i=0;i<n-1;i++)
  82. 		{
  83. 			if(s[i]==s[i+1])
  84. 			pal[i][i+1]=1;
  85. 		}
  86.  
  87. 		for(int i=2;i<n;i++)
  88. 		{
  89. 			for(int j=0;j+i<n;j++)
  90. 			{
  91. 				if(s[j]==s[j+i] and pal[j+1][j+i-1]==1)
  92. 				pal[j][j+i]=1;
  93. 			}
  94. 		}
  95. 		// code ends/////
  96. 		//for(int i=0;i<n;i++)
  97. 		//{
  98. 			//for(int j=0;j<n;j++)
  99. 			//cout<<pal[i][j]<<" ";
  100. 			//cout<<"\n";
  101. 		//}
  102.  
  103. 		cout<<palindrome_partition(s,0,n-1)<<"\n";
  104. 	}
  105.     auto finish = chrono::high_resolution_clock::now();
  106.     cerr << "Time elapsed: " << (chrono::duration<long double>(finish-start)).count() << "s\n";
  107.     return 0;
  108.  
  109. }
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
Success #stdin #stdout #stderr 2.08s 13064KB
comments (?)
stdin
copy 
1
"apjesgpsxoeiokmqmfgvjslcjukbqxpsobyhjpbgdfruqdkeiszrlmtwgfxyfostpqczidfljwfbbrflkgdvtytbgqalguewnhvvmcgxboycffopmtmhtfizxkmeftcucxpobxmelmjtuzigsxnncxpaibgpuijwhankxbplpyejxmrrjgeoevqozwdtgospohznkoyzocjlracchjqnggbfeebmuvbicbvmpuleywrpzwsihivnrwtxcukwplgtobhgxukwrdlszfaiqxwjvrgxnsveedxseeyeykarqnjrtlaliyudpacctzizcftjlunlgnfwcqqxcqikocqffsjyurzwysfjmswvhbrmshjuzsgpwyubtfbnwajuvrfhlccvfwhxfqthkcwhatktymgxostjlztwdxritygbrbibdgkezvzajizxasjnrcjwzdfvdnwwqeyumkamhzoqhnqjfzwzbixclcxqrtniznemxeahfozp"
stdout
copy 
454
stderr
copy 
Time elapsed: 2.07689s
https://ideone.com/gE1NoM
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!