Advertisement
OIQ

Untitled

OIQ
Dec 8th, 2019
180
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.81 KB | None
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. int main() {
  9.  
  10.     int n;
  11.  
  12.     cin >> n;
  13.  
  14.     vector <int> a(n);
  15.  
  16.     for (int i = 0; i < n; i++) cin >> a[i];
  17.  
  18.     vector <vector<int>> dp(n, vector<int>(n, 0));
  19.  
  20.     for (int len = 2; len <= n; len++) {
  21.         for (int left = 0; left + len - 1 < n; left++) {
  22.             int right = left + len - 1;
  23.             if (len == 2)
  24.                 dp[left][right] = 0;
  25.             else {
  26.                 dp[left][right] = 1000 * 1000 * 1000;
  27.                 for (int mid = left + 1; mid <= right - 1; mid++)
  28.                     dp[left][right] = min(dp[left][right], (a[left] + a[right]) * a[mid] + dp[left][mid] + dp[mid][right]);
  29.             }
  30.         }
  31.     }
  32.  
  33.     cout << dp[0][n - 1];
  34.  
  35.     return 0;
  36. }
Advertisement
RAW Paste Data Copied
Advertisement