fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <map>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <set>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdlib>
  11. #include <string>
  12. #include <list>
  13. #include <bitset>
  14. #include <iomanip>
  15. #include <cmath>
  16. #include <sstream>
  17. #include <deque>
  18. #include <climits>
  19. #include <cassert>
  20. using namespace std;
  21. typedef unsigned long long ull;
  22. typedef long long ll;
  23. #define Max(x,y) ((x)>(y)?(x):(y))
  24. #define Min(x,y) ((x)<(y)?(x):(y))
  25. #define sll(x) scanf("%lld",&x)
  26. #define sull(x) scanf("%llu",&x)
  27. #define si(x) scanf("%d",&x)
  28. #define ISF(x) getline(cin,x)
  29. #define pii pair<int,int>
  30. #define pll pair<ll,ll>
  31. #define pps pair<ll,pll>
  32. #define ppf pair<pll,ll>
  33. #define psi pair<string,int>
  34. #define pis pair<int,string>
  35. #define fr first
  36. #define se second
  37. #define MOD 1000000007
  38. #define MP(x,y) make_pair(x,y)
  39. #define eps 1e-7
  40. #define V(x) vector<x>
  41. #define pb(x) push_back(x)
  42. #define mem(x,i) memset(x,i,sizeof(x))
  43. #define fori(i,s,n) for(i=(s);i<(n);i++)
  44. #define ford(i,s,n) for(i=(n);i>=(s);--i)
  45. #define INF 8944674407370955161LL
  46. #define debug(i,st,arr) fori(i,0,st){cout<<arr[i]<<" ";}cout<<endl;
  47. #define forci(i,sw) for((i)=(sw).begin();(i)!=(sw).end();(i)++)
  48. #define forcd(i,sw) for((i)=(sw).rbegin();(i)!=(sw).rend();(i)++)
  49. #define ck(t)	clock_t t = clock()
  50. int abs(int x) {if(x < 0) return -x; return x;}
  51. inline int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);}
  52. /*inline int readint( )
  53. {
  54. 	int n = 0 , s = 1 ; char p = getchar_unlocked( ) ;
  55. 	if(p == '-') s = -1 ;
  56. 	while((p < '0' || p > '9') && p != EOF && p != '-')
  57. 		p = getchar_unlocked( ) ;
  58. 	if(p == '-') s=-1 , p=getchar_unlocked( );
  59. 	while(p >= '0' && p <= '9')
  60. 		n = (n << 3) + (n << 1) + (p - '0'), p = getchar_unlocked( ) ;
  61. 	return n * s ;
  62. }*/
  63. int main()
  64. {
  65. 	int t;
  66. 	scanf("%d",&t);
  67. 	while(t--)
  68. 	{
  69. 		int n;
  70. 		scanf("%d",&n);
  71. 		char s[100];
  72. 		scanf("%s",s);
  73. 		bool isp[100][100];
  74. 		int dp[100];
  75. 		for(int i=0;i<n;i++)
  76. 			for(int j=0;j<n;j++)
  77. 				isp[i][j]=false;
  78. 		for(int i=0;i<n;i++)
  79. 		{
  80. 			isp[i][i]=true;
  81. 			if(i<n-1)
  82. 			{
  83. 				if(s[i]==s[i+1])
  84. 					isp[i][i+1]=true;
  85. 			}
  86. 		}
  87. 		for(int i=3;i<=n;i++)
  88. 			for(int j=0;j<=n-i;j++)
  89. 				if(s[j]==s[i+j-1])
  90. 				{
  91. 					if(isp[j+1][i+j-2])
  92. 						isp[j][i+j-1]=true;
  93. 				}
  94. 		int min;
  95. 		int t=1;
  96. 		for(int i=0;i<n;i++)
  97. 		{
  98.  
  99. 			if(isp[0][i]){
  100. 			//	min=1;
  101. 				dp[i]=1;
  102. 				continue;
  103. 			}
  104. 			for(int j=0;j<=i;j++)
  105. 			{
  106.  
  107. 				if(isp[j][i])
  108. 				{
  109. 					if(j>0&&j!=i)
  110. 					{
  111. 						dp[i]=dp[j-1]+1;
  112. 						break;
  113. 					}
  114. 					if(i==j&&j>0)
  115. 						dp[i]=dp[j-1]+1;
  116. 				}
  117. 			}
  118. 		}
  119. 		printf("%d\n",dp[n-1]);			
  120. 	}
  121. 	return 0;
  122. }
Success #stdin #stdout 0s 2688KB
comments (?)
stdin
copy 
1
7
abccbda
stdout
copy 
4
https://ideone.com/Pn3fpM
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!