Skip to content

Instantly share code, notes, and snippets.

@vaibsharma
Created February 7, 2018 04:42
Show Gist options
  • Save vaibsharma/8e3096c212e609ee05328bdbda0db144 to your computer and use it in GitHub Desktop.
Save vaibsharma/8e3096c212e609ee05328bdbda0db144 to your computer and use it in GitHub Desktop.
SPOJ - MIXTURES
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment