Spoj Problem MIXTURES - Mixtures[Java Solution] using Dynamic Programming

     Spoj Problem MIXTURES - Mixtures[Java Solution]                                           using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/MIXTURES/

Hint:- Matrix Chain Multiplication Algorithm.

Helpful Tutorial for Matrix Chain Multiplication Problem using Dynamic Programming:-

With the help of algorithm of  Matrix Chain Multiplication,this problem can be solved similarly except we have to also store new generated color.Keep in mind that we have to minimize the generated smoke.It is an advice to try yourself to solve the problem after studying the concept of Matrix Chain Multiplication using Dynamic Programming.Here,a solution for this problem written in java is given below:-

Java Program:-

/**
 * @(#)MIXTURES.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/4/14
 */

import java.io.*;

class MIXTURES {

    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
    String in;
   
    while((in=br.readLine())!=null){
   
    int N=Integer.parseInt(in);
    String str[]=br.readLine().split(" ");
    int ar[]=new int[N];
   
    for(int i=0;i<N;i++){
    ar[i]=Integer.parseInt(str[i]);
    }
   
    System.out.println(MCM(ar));
   
    }
   
    }
 
    static int MCM(int ar[]){
   
    if(ar.length==2){
    return ar[0]*ar[1];
    }
   
    int dp[][]=new int[ar.length][ar.length];
    int color[][]=new int[ar.length][ar.length];
   
    for(int i=0;i<ar.length;i++){
    color[i][i]=ar[i];
    }
   
    int mul=0;
   
    for(int l=2;l<=ar.length;l++){
   
    for(int i=0;i<=ar.length-l;i++){
   
    int j=i+l-1;
    dp[i][j]=Integer.MAX_VALUE;
    for(int k=i;k<j;k++){
    mul=dp[i][k]+dp[k+1][j]+(color[i][k]*color[k+1][j]);
    if(mul<dp[i][j]){
    dp[i][j]=mul;
    color[i][j]=(color[i][k]+color[k+1][j])%100;
    }
    }
   
    }
   
    }
    return dp[0][ar.length-1];
   
    }
 
 
}

Input:-

2
18 19
3
40 60 20

Output:-

342
2400

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------