MIXTURES - Mixtures - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : MIXTURES

👉 Hint : Simple DP

✅ C++ Solution :

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

int arr[101];
int dp[101][101];
int color[101][101];
int main()
{
	int n,i,j,ans;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
			cin>>arr[i];
		for(int i=1;i<=n;i++)
		{
			color[i][i]=arr[i];
			dp[i][i]=0;
		}
		int ans;	
		for(int k=2;k<=n;k++)
		{
			for(i=1,j=k;i<=n,j<=n;i++,j++)
			{
			    dp[i][j]=INT_MAX;
			    
			    for(int p=i;p<j;p++)
			    {
			        if((color[i][p]*color[p+1][j])+dp[i][p]+dp[p+1][j]<dp[i][j])
			        {
			            dp[i][j]=(color[i][p]*color[p+1][j])+dp[i][p]+dp[p+1][j];
			            color[i][j]=(color[i][p]+color[p+1][j])%100;
			        }
			    }
			
			}
		}
		cout<<dp[1][n]<<endl;
	}
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.