fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int dp[1010];
  7.  
  8. void f(int k, string z, string x, int kk) {
  9. 	int i, j, n = x.length();
  10. 	for(i = 1; i <= n; ++i) {
  11. 		if(n%i == 0) {
  12. 			string q = x.substr(0, i), p = "";
  13. 			for(j = 0; j < n/i; ++j)
  14. 				p += q;
  15. 			if (p == x) {
  16. 				if(i <= z.length() and z.find(q) != string::npos)
  17. 					dp[k] = min(dp[k], dp[kk-1] + 1 + n/i);
  18. 			}
  19. 		}
  20. 	}
  21. }
  22.  
  23. int main() {
  24. 	int t, i, j, tc = 0, n;
  25. 	cin >> t;
  26. 	while(t--) {
  27. 		tc++;
  28. 		cout << "Case #" << tc << ": ";
  29. 		string s;
  30. 		cin >> s;
  31. 		n = s.length();
  32. 		dp[0] = 1;
  33. 		dp[1] = 2;
  34. 		for(i = 2; i < n; ++i) {
  35. 			dp[i] = dp[i-1] + 1;
  36. 			string x = "";
  37. 			x += s[i];
  38. 			for(j = i - 1; j >= 1; --j) {
  39. 				x = s[j] + x;
  40. 				// cout << i << " " << j << endl;
  41. 				string z = s.substr(0, j);
  42. 				f(i, z, x, j);
  43. 			}
  44. 			// cout << dp[i] << endl;
  45. 		}
  46. 		cout << dp[n-1] << endl;
  47. 	}
  48. 	return 0;
  49. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/B5inJR
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!