Advertisement
SuitNdtie

MTrap DP chain matrix

May 4th, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.71 KB | None | 0 0
  1. #include<stdio.h>
  2. typedef long long int ll;
  3.  
  4. ll arr[210];
  5.  
  6. ll min(ll a,ll b){
  7.     return (a < b ? a : b);
  8. }
  9.  
  10. ll dp[210][210];
  11.  
  12. ll cal(int L,int R){
  13.     if(L == R){
  14.         return 0;
  15.     }
  16.     if(dp[L][R] != -1)return dp[L][R];
  17.    
  18.     ll mina = 1e18;
  19.     for(int m = L ; m < R ; m ++){
  20.         mina = min(mina , cal(L,m) + cal(m+1,R) + (arr[L-1] * arr[m] * arr[R]));
  21.     }
  22. //  printf("Test (%d,%d) : %lld\n",L,R,mina);
  23.     return dp[L][R] = mina;
  24. }
  25.  
  26. int main()
  27. {
  28.     for(int i = 0 ; i < 210 ; i ++)for(int j = 0 ; j < 210 ; j ++)dp[i][j] = -1;
  29.     int n;
  30.     scanf("%d",&n);
  31.     for(int i = 0 ; i < n -1 ; i ++){
  32.         ll x;
  33.         scanf("%lld %lld",&arr[i],&x);
  34.     }
  35.     scanf("%lld %lld",&arr[n-1],&arr[n]);
  36.    
  37.     printf("%lld",cal(1,n));
  38.     return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement