v 0. Pasted by slipstak2 as cpp at 2011-10-28 19:46:07 MSK and set expiration to never.

Paste will expire never.

  1. // Очно-заочный кружок
  2. // Занятие №8. Дополнительные олимпиадные задачи
  3. // Задача A. Электронная почта
  4. // ibelyaev: 26Oct2011
  5. // http://cppalgo.blogspot.com/2011/04/blog-post.html
  6.  
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <algorithm>
  10. #include <string>
  11. #include <string.h>
  12. #include <cmath>
  13. #include <queue>
  14. #include <vector>
  15. #include <map>
  16. #include <stdlib.h> // for exit(0)
  17. #include <stack>
  18. #include <list>
  19. #include <ctime>
  20. #include <set>
  21.  
  22. using namespace std;
  23.  
  24. const int MAX_VAL = 1e9;
  25. int n;
  26. vector<int> a;
  27. vector<vector<int> > dp;
  28. void input(){
  29.     scanf("%d", &n);
  30.     a.resize(n);
  31.     dp.resize(n,vector<int>(n,MAX_VAL));
  32.     for (int i=0;i<n;++i)
  33.         scanf("%d", &a[i]);
  34. }
  35. int solve(int l, int r) {
  36.     if (l > r) return 0;
  37.     if (l == r) return 1;
  38.     int &ref = dp[l][r];
  39.     if (ref != MAX_VAL) return ref;
  40.     for (int k = l; k < r; ++k)
  41.         ref = min(ref, solve(l,k) + solve(k+1,r));
  42.  
  43.     if (a[l] == a[r]) {
  44.         ref = min(ref, solve(l + 1, r - 1) + 1);
  45.         for (int k = l + 1; k <= r - 1; ++k) {
  46.             ref = min(ref,
  47.                   min(solve(l,k) + solve(k+1,r-1),
  48.                       solve(l+1,k-1) + solve(k,r)));
  49.         }
  50.     }
  51.     return ref;
  52. }
  53. int main()
  54. {
  55.     freopen("input.txt","r",stdin);
  56.     freopen("output.txt","w",stdout);
  57.  
  58.     input();
  59.     printf("%d",solve(0,n-1));
  60.  
  61.     return 0;
  62. }


Editing is locked.