初入算法篇（动态规划）URAL1167

最新推荐文章于 2018-07-16 23:40:54 发布

keepcoral

最新推荐文章于 2018-07-16 23:40:54 发布

阅读量286

点赞数

分类专栏：动态规划

本文链接：https://blog.csdn.net/keepcoral/article/details/79997607

版权

动态规划专栏收录该内容

13 篇文章

订阅专栏

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 P _{1 horses in the first stable, the next P_{2 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 j white 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.

Example

input	output
6 3 1 1 0 1 0 1	2

Notes

Place the first 2 horses in the first stable, the next 3 horses in the 2nd stable and the last horse in the 3rd stable.

抽象成模型，有k个盒子，有n个黑白小球，a个黑球和b个白球放在同一个盒子不愉快值为a*b,要按顺序把求放入所有盒子中，要求不能有空盒子，求最小不愉快值

动态规划思想，先求出所有区间的不愉快值，即先求出所有区间的黑白小球的个数，然后dp[i][j]表示将第j个小球放入第i个盒子中，将（1，j）个所有区间都枚举一次取得最小值即为dp[i][j]的值，转移方程为dp[i][j]=min(dp[i-1][t-1]+sum[t][j]) t=(1,j)

详情看代码注释

#include<cstdio>
#include<iostream>
#define MAXN 999999
using namespace std;
int a[509];
int b[509][509],c[509][509];
int dp[509][509];
int sum[509][509];
int main()
{
    int n,k,i,j,t,M;
   scanf("%d%d",&n,&k);
   for(i=1;i<=n;i++)
   {
       scanf("%d",&a[i]);
       dp[0][i]=MAXN;//将马不放入盒子是不符合题意的
   }
   for(i=1;i<=n;i++)//马数区间（i,j）和
   {
       for(j=i;j<=n;j++)//i代表从第i匹马开始遍历区间
       {
           if(a[j]==1)
           {
               b[i][j]=b[i][j-1]+1;
               c[i][j]=c[i][j-1];
           }
           else
           {
               c[i][j]=c[i][j-1]+1;
               b[i][j]=b[i][j-1];
           }
           sum[i][j]=b[i][j]*c[i][j];//白马和黑马乘积为不愉快值
       }
   }
   for(i=1;i<=k;i++)//第i个盒子
   {
       for(j=1;j<=n;j++)//第j匹马
       {
           M=MAXN;//先初始化为最大值，防止出现空盒子
           for(t=1;t<=j;t++)//dp[i][j]的意义是将第j匹马放入第i个盒子中
           {
               //dp[i-1][t-1]表示将前t-1匹马放入前i-1个盒子中的最小不愉快值
               if(dp[i-1][t-1]+sum[t][j]<M)//sum[t][j]表示t到j区间的不愉快值
               {
                   M=dp[i-1][t-1]+sum[t][j];
               }//这是枚举所有区间情况
           }
           dp[i][j]=M;//将j匹马放入i个盒子的最小不愉快值
       }
   }
   printf("%d\n",dp[k][n]);
}