Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- typedef long long int ll;
- ll arr[210];
- ll min(ll a,ll b){
- return (a < b ? a : b);
- }
- ll dp[210][210];
- ll cal(int L,int R){
- if(L == R){
- return 0;
- }
- if(dp[L][R] != -1)return dp[L][R];
- ll mina = 1e18;
- for(int m = L ; m < R ; m ++){
- mina = min(mina , cal(L,m) + cal(m+1,R) + (arr[L-1] * arr[m] * arr[R]));
- }
- // printf("Test (%d,%d) : %lld\n",L,R,mina);
- return dp[L][R] = mina;
- }
- int main()
- {
- for(int i = 0 ; i < 210 ; i ++)for(int j = 0 ; j < 210 ; j ++)dp[i][j] = -1;
- int n;
- scanf("%d",&n);
- for(int i = 0 ; i < n -1 ; i ++){
- ll x;
- scanf("%lld %lld",&arr[i],&x);
- }
- scanf("%lld %lld",&arr[n-1],&arr[n]);
- printf("%lld",cal(1,n));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement