v 0. Pasted by slipstak2 as cpp at 2011-01-06 17:24:55 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 12.
  2. // 12C. Головоломка умножения [mpuzzle]
  3. // ibelyaev: 02Jan2011
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <cstdio>
  8.  
  9. using namespace std;
  10.  
  11. int n;
  12. vector<int> mas;
  13. vector<vector<int> > mem;
  14. void input()
  15. {
  16.     cin>>n;
  17.     mas.resize(n);
  18.     for (int i=0;i<n;i++)
  19.         cin>>mas[i];
  20.     mem = vector<vector<int> > (n,vector<int>(n));
  21. }
  22.  
  23. void solve()
  24. {
  25.     for (int len = 2; len < n; len++)
  26.     {
  27.         for (int i=0;i<n;i++)
  28.         {
  29.             int j = i + len;
  30.             if (j == n)
  31.                 break;
  32.             int res = 1e9;
  33.             for (int m = i+1; m<=j-1; m++)
  34.             {
  35.                 int cur = mem[i][m] + mas[i] * mas[m] * mas[j] + mem[m][j];
  36.                 res = min(res,cur);
  37.             }
  38.             mem[i][j] = res;
  39.         }
  40.     }
  41.     cout<<mem[0][n-1];
  42. }
  43. int main()
  44. {
  45.     freopen("input.txt","r",stdin);
  46.     freopen("output.txt","w",stdout);
  47.  
  48.     input();
  49.     solve();
  50.     return 0;
  51. }


Editing is locked.