SPOJ - MIXTURES

mixtures.cpp

#include<bits/stdc++.h>
 
using namespace std;

/**
 * Initializing global array for dp and sum
 */

int dp[107][107];
int sum[107][107];

/**
 * Function to calculate minimum cost in range of (l,r)
 * @param {int,int}
 * @return int minimum cost
 */

int find(int l, int r){
	if(l>=r) return 0;
	if(dp[l][r]!=-1) return dp[l][r];
	int a,b,mn = INT_MAX;
	for(int x=l;x<r;x++){
		a = sum[l][x];
		b = sum[x+1][r];
		mn = min(mn, a*b + find(l,x) + find(x+1,r));
	}
	dp[l][r] = mn;
	return mn;
}
 
int main(){
	int n,i;
	string a;
	while(scanf("%d",&n) != EOF){
		vector<int> p;
		memset(dp,-1,sizeof(dp));
		memset(sum,0,sizeof(sum));
		for(int x=0;x<n;x++){
			scanf("%d",&i);
			p.push_back(i);
			sum[x][x] = i;
		}
    
    /**
     * Creating the mixture for the given range (x,i) x<i
     */
    
		for(int x=0;x<n;x++){
			for(int i=x+1;i<n;i++){
				sum[x][i] = (sum[x][i-1]+p[i])%100;
			}
		}
		cout<<find(0,n-1)<<"\n";
	}
	return 0;
}