fork(19) download
  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
stdin
3
1 2 1
stdout
1