【Ural1167】 Bicolored Horses——基础Dp

69 阅读 0 评论 46 点赞

我是靠谱客的博主舒服寒风，最近开发中收集的这篇文章主要介绍【Ural1167】 Bicolored Horses——基础Dp，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 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.
Sample

input

6 3
1
1
0
1
0
1

output

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.

题意：农夫将让马排成一列按照顺序进入马厩，一个马厩的不愉快的值是这个马厩中的白马与黑马的数量的乘积，求最小的不愉快的和，要求每一个马厩中至少有一匹马
思路：Dp[i][j] 表示在第i个马厩中安置第j头马时的不愉快的和，所以对于第i个马厩的不愉快值取决于第i-1个马厩的安排Dp[i][j] = min(Dp[i][j],Dp[i-1][k]+(Bnum[j]-Bnum[k])*(Wnum[j]-Wnum[k])),由于每一个马厩都有马，所以在初始化的时候要特殊处理

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

const int Max = 550;

int Dp[Max][Max];

int a[Max];

int B[Max],W[Max];//黑马与白马的前缀和数组

int main()
{
    int n,m;

    while(~scanf("%d %d",&n,&m))
    {
        memset(Dp,INF,sizeof(Dp));//初始化为无穷大，保证一定有马。

        B[0]  = W[0] = 0;

        for(int i = 1;i<=n;i++)
        {
            scanf("%d",&a[i]);

            B[i]= B[i-1];

            W[i]=W[i-1];

            if(a[i]) B[i]++;

            else W[i]++;
        }

        int ans =0,ant= 0;

        for(int i =1;i<=n-(m-1);i++)//首先处理第一个马厩，同时保证后面的马厩有马，所有最多马的数量为n-m+1.
        {

            Dp[1][i] = W[i]*B[i];
        }

        for(int i = 2;i<=m;i++)
        {
            for(int j = i-1;j<=n-(m-i+1);j++)
            {
                for(int k = j+1;k<=n-(m-i);k++)
                {
                    Dp[i][k] = min(Dp[i-1][j]+(B[k]-B[j])*(W[k]-W[j]),Dp[i][k]);//当第i-1个马厩的最后一头马是第j头的时候，第i个马厩的最后一头马是第k头的时候的最小的不愉快值。
                }
            }
        }
        cout<<Dp[m][n]<<endl;
    }
    return 0;
}