fork(22) download
copy 
  1. #include<algorithm>
  2. #include<cstdio>
  3. using namespace std;
  4. const int maxn=505;
  5.  
  6. int n, a[maxn], d[maxn][maxn];
  7.  
  8. void read() {
  9. 	scanf("%d", &n);
  10. 	for (int i = 0; i < n; i++) {
  11. 		scanf("%d", a + i);
  12. 	}
  13. }
  14.  
  15. void fun() {
  16. 	for (int len = 1; len <= n; len++) {
  17. 		for (int beg = 0, end = len - 1; end < n; beg++, end++) {
  18. 			if (len == 1) {
  19. 				d[beg][end] = 1;
  20. 			} else {
  21. 				d[beg][end] = 1 + d[beg + 1][end];
  22. 				if (a[beg] == a[beg + 1]) {
  23. 					d[beg][end] = min(1 + d[beg + 2][end], d[beg][end]);
  24. 				}
  25. 				for (int match = beg + 2; match <= end; match++) {
  26. 					if (a[beg] == a[match]) {
  27. 						d[beg][end] = min(d[beg + 1][match - 1] + d[match + 1][end], d[beg][end]);
  28. 					}
  29. 				}
  30. 			}
  31. 		}
  32. 	}
  33. }
  34.  
  35. int main() {
  36. 	read();
  37. 	fun();
  38. 	printf("%d\n", d[0][n-1]);
  39. 	return 0;
  40. }
  41.  
Success #stdin #stdout 0s 4456KB
comments (?)
stdin
copy 
3
1 2 1
stdout
copy 
1
https://ideone.com/Aw1bSs
language:
C++14 (gcc 8.3)
created:
8 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!