fork(2) download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <cctype>
  20. #include <string>
  21. #include <cstring>
  22. #include <cstdio>
  23. #include <cmath>
  24. #include <cstdlib>
  25. #include <ctime>
  26. #include <climits>
  27. #include <istream>
  28. #include <fstream>
  29. #include <iterator>
  30. #include <utility>
  31.  
  32. using namespace std;
  33.  
  34. int matrix_chain(vector<int>a,int len){
  35.     int val;
  36.     int total = 0;
  37.     int min;
  38.     int mid;
  39.     while(a.size()>=3){
  40.         min = INT_MAX;
  41.         for(int i=0;i<a.size()-2;i++){
  42.             val = a[i]*a[i+2];
  43.             if(min>val){
  44.                 min = val;
  45.                 mid = i+1;
  46.             }
  47.         }
  48.         min = min*a[mid];
  49.         total+=min;
  50.         a.erase(a.begin()+mid);
  51.     }
  52.     return total;
  53. }
  54.  
  55. int main(int argc, char** argv) {
  56.     int t;
  57.     cin>>t;
  58.     vector<int>arr;
  59.     for(int i=0;i<t;i++) {
  60.         int val;
  61.         cin>>val;
  62.         arr.push_back(val);
  63.     }
  64.     cout<<matrix_chain(arr,t)<<endl;
  65.     return 0;
  66. }
  67.  
  68.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
5
40 20 30 10 30
stdout
copy 
26000
https://ideone.com/tU8ckl
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!