1167. Bicolored Horses Time limit: 1.0 second Memory limit: 64 MB Every day, farmer Ion (this is a Romanian name) takes out all his horses, so they may run and play. When they are done, farmer Ion has to take all the horses back to the stables. In order to do this, he places them in a straight line and they follow him to the stables. Because they are very tired, farmer Ion decides that he doesn't want to make the horses move more than they should. So he develops this algorithm: he places the 1st P1 horses in the first stable, the next P2 in the 2nd stable and so on. Moreover, he doesn't want any of the K stables he owns to be empty, and no horse must be left outside. Now you should know that farmer Ion only has black or white horses, which don't really get along too well. If there are i black horses and jwhite horses in one stable, then the coefficient of unhappiness of that stable is i*j. The total coefficient of unhappiness is the sum of the coefficients of unhappiness of every of the K stables. Determine a way to place the N horses into the K stables, so that the total coefficient of unhappiness is minimized. Input On the 1st line there are 2 numbers: N (1 ≤ N ≤ 500) and K (1 ≤ K ≤ N). On the next N lines there are N numbers. The i-th of these lines contains the color of the i-th horse in the sequence: 1 means that the horse is black, 0 means that the horse is white. Output You should only output a single number, which is the minimum possible value for the total coefficient of unhappiness. Sample input output 6 3 1 1 0 1 0 1 This question gives us some good insight when thought recursively. Much like matrix chain mulitiplication we need to parenthesise the given sequence such that the cost is  minimum with the given parameters. Here we call the solvefunction with (0,K-1) as the initial index is 0 and then we need to  paranthesise the sequence in K-1 portions.   The for loop is interesting one  else { dp[k][index]=10000000; for(int i=index+1;i<=n-k;i++) { // dp[k][i]=INT_MAX; int horses=i-index; int unhappy=(horses-(black[i]-black[index]))*(black[i]-black[index]); dp[k][index]=min(dp[k][index],unhappy+solve(k-1,i)); } } Here we try to allocate horses in the current stable from index+1 to n-k (as we need to allocate  minimum one horse in a stable). Then we calculate the unhappy quotient as number of white*black horses in the range (index to i). Then we calculate dp[index][i]. when solve is called with k=0(we return the quotient of unhappiness assumming all left horses are  to be assigned to the last stable) **** the code goes here*** #include<iostream> #include<stdio.h> using namespace std; int dp[550][550]; int black[10000]; int arr[550]; int n; int solve(int k, int index) { //cout<<index<<" "<<k<<endl; if(dp[k][index]!=-1) { return dp[k][index]; } if(k==0) { int calc=((n-index)-(black[n]-black[index]))*(black[n]-black[index]); return calc; } else { dp[k][index]=10000000; for(int i=index+1;i<=n-k;i++) { // dp[k][i]=INT_MAX; int horses=i-index; int unhappy=(horses-(black[i]-black[index]))*(black[i]-black[index]); dp[k][index]=min(dp[k][index],unhappy+solve(k-1,i)); } } return dp[k][index]; } int main() { int K; cin>>n>>K; for(int i=1;i<=n;i++) { cin>>arr[i]; black[i]=black[i-1]; if(arr[i]==1) { black[i]++; } } for(int i=0;i<=510;i++) { for(int k=0;k<=510;k++) { dp[i][k]=-1; } } cout<<solve(K-1,0); } 2