## Algoritmo de Matrix Chain Multiplication.

Cualquier duda no dudes en contactar.

``````/*
Matrix Chain Multiplication

0     1     2     3
[2,3] [3,6] [6,4] [4,5]

1 -> (0,1)(2,3) = 2*3*6+6*4*5+2*6*5 = 36 + 120 + 60 = 216
2 -> ((0,1)2))3 = 2*3*6+2*6*4+2*4*5 = 36 + 48 + 40 = 216

0 | 1 | 2 | 3
0 | 0   36  84 124
1 |     0   72 132
2 |         0  120
3 |             0

l = 1 sera siempre 0 porque estamos cogiendo la misma matriz consigo mismo
l = 2
(0,1) 2*3*6 = 36
(1,2) 3*6*4 = 72
(2,3) 6*4*5 = 120
l = 3
(0,1,2) = (0,1)(2,2)
1. (1,2)+2*3*4 = 96
2. (0,1)+2*6*4 = 84
(1,2,3) = (1,2)(3,3)
1. (2,3)+3*6*5 = 210
2. (1,2)+3*4*5 = 132
l = 4
(0,1,2,3) = (0,1)(2,2)
1. 0*(1,2,3) = 132+2*3*5 = 162
2. (0,1)*(2,3) = 32+120+2*6*5=216
3. (0,1,2)*3 = 84+2*4*5= 124

T[i][j] = min {T[i][k]+T[k+1][j]+val[i].first*val[k].second*val[j].second}

*/
/*
#include <bits/stdc++.h>
#define INF 0x3F3F3F3F
#define n 4
using namespace std;

int arr[] = {1, 2, 3, 4};
int dp[n][n];

int topDown(int i, int j)
{
if(i==j) return 0;
if(dp[i][j]!=-1) return dp[i][j];
dp[i][j]=INF;
for(int k=i; k<=j;k++)
{
int temp = topDown(i,k)+topDown(k+1,j)+arr[i-1]*arr[k]*arr[j];
dp[i][j]=min(dp[i][j],temp);
}
return dp[i][j];
}

int main()
{
memset(dp,-1,sizeof(dp));
int m[n][n];

for (int i=1; i<n; i++) m[i][i] = 0; // cost is zero when multiplying one matrix.

for (int L=2; L<n; L++) // L is chain length.
for (int i=1; i<n-L+1; i++)
{
int j = i+L-1;
m[i][j] = INT_MAX;
for (int k=i; k<=j-1; k++)
{
// q = cost/scalar multiplications
int q = m[i][k] + m[k+1][j] + arr[i-1]*arr[k]*arr[j];
if (q < m[i][j])  m[i][j] = q;
}
}

cout<<m[1][n-1]<<endl;
cout<<topDown(1,n-1)<<endl;
return 0;
}
*/

#include <bits/stdc++.h>
#define INF 0x3F3F3F3F
using namespace std;

long long int dp[105][105];
long long int arr[105];

long long int sum(int j,int e)
{
long long res=0;
for(int i=j; i<=e;i++)
{
res+=arr[i];
res%=100;
}
return res;
}
long long int solve(int i, int j)
{
if(i>=j) return 0;
if(dp[i][j]!=-1) return dp[i][j];
dp[i][j]=INF;
for(int k=i; k<=j;k++)
{
long long int temp = solve(i,k)+solve(k+1,j);
temp+=sum(i,k)*sum(k+1,j); //arr[i-1]*arr[k]*arr[j];
dp[i][j]=min(dp[i][j],temp);
//dp[i][j] =min(dp[i][j],solve(i,k)+solve(k+1,j)+sum(i,k)*sum(k+1,j));
}
return dp[i][j];
}

int main()
{
freopen("C:/Users/Isaac/Documents/QT/Entregar/in.txt","r",stdin);
//freopen("C:/Users/Isaac/Documents/QT/Entregar/out.txt","w",stdout);
int n;
while(scanf("%d",&n)==1)
{
memset(dp,-1,sizeof(dp));
for(int i=0; i<n;i++) { cin>>arr[i]; color[i][i]=arr[i]; }
cout<<solve(0,n-1)<<'\n';
}
return 0;
}

``````