(SPOJ) 345. Mixtures

/*
user: hasib
time: 0.07 sec
link: http://www.spoj.com/problems/MIXTURES/
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<sstream>


#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define pb push_back
#define sf scanf
#define pf printf
#define getint(a) sf("%d", &a)
#define INF 1<<29
#define SZ(v) int(v.size())
#define pi acos(-1.0)
#define all(v) v.begin(), v.end()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)

using namespace std;


#define MAXX 101
#define type int




int number_of_color;
int colors[MAXX];

type dp[MAXX][MAXX];
int new_color[MAXX][MAXX];

type rec(int s, int e)
{


    type &ret = dp[s][e];
    if(ret != -1) return ret;


    if(s + 1 == e )
    {
        new_color[s][e] = (colors[s] + colors[e]) % 100;
        return ret = (colors[s] * colors[e]);
    }
    else if(s==e)
    {
        new_color[s][e] = colors[s];
        return ret = 0;
    }


    ret = INF;


    for(int i=s; i<e; i++)
    {
        rec(s, i);
        rec(i+1, e);
        if( rec(s, i) + rec(i+1, e) + (new_color[s][i] * new_color[i+1][e]) < ret )
        {
            new_color[s][e] = (new_color[s][i] + new_color[i+1][e]) % 100;
            ret = rec(s, i) + rec(i+1, e) + (new_color[s][i] * new_color[i+1][e]);
        }
    }

    return ret;
}






int main()
{
    while(getint(number_of_color) == 1)
    {
        loop(i, number_of_color)
        {
            getint(colors[i]);
        }
        mem(dp, -1);
        cout<<rec(0, number_of_color - 1)<<endl;
    }

    return 0;



}