RQN 273 马棚问题 dp

PID273 / 马棚问题 

2016-07-29 18:21:55

运行耗时：1624 ms

运行内存：16248 KB

题目描述

每天，小明和他的马外出，然后他们一边跑一边玩耍。当他们结束的时候，必须带所有的马返回马棚，小明有K个马棚。他把他的马排成一排然后跟随它走向马棚， 因为他们非常疲劳，小明不想让他的马做过多的移动。因此他想了一个办法：将马按照顺序放在马棚中，后面的马放的马棚的序号不会大于前面的马放的马棚的序 号。而且，他不想他的K个马棚中任何一个空置，也不想任何一匹马在外面。已知共有黑、白两种马，而且它们相处得并不十分融洽。如果有i个白马和j个黑马在 一个马棚中，那么这个马棚的不愉快系数将是i*j。所有k个马棚不愉快系数的和就是系数总和。确定一种方法把n匹马放入k个马棚，使得系数总和最小。

输入格式

输入：在第一行有两个数字：n（1≤n≤500）和k（1≤k≤n）。在接下来的n行是n个数。在这些行中的第i行代表队列中的第i匹马的颜色：1意味着马是黑色的，0意味着马是白色的。

输出格式

输出：只输出一个单一的数字，代表系数总和可能达到的最小值。

样例输入 6 3 {6匹马，3个马棚}
1 {第1匹马为黑马}
1
0 {第3匹马为白马}
1
0
1

样例输出 2 {最小系数总和}

思路：dp[i][t]=min(dp[i][t],dp[j][t-1]+(h[i]-h[j])*(b[i]-b[j]));

　     dp[i][t]表示第i匹马放入第t个马棚的最小答案；

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll __int64

#define esp 0.00000000001

const int N=1e3+,M=1e6+,inf=1e9+,mod=;

int a[N];

int h[N];

int b[N];

int dp[N][N];

int main()

{

    int x,y,z,i,t;

    while(~scanf("%d%d",&x,&y))

    {

        for(i=; i<=x; i++)

            for(t=; t<=y; t++)

            dp[i][t]=inf;

        dp[][]=;

        for(i=;i<=x;i++)

        {

            scanf("%d",&a[i]);

            h[i]=h[i-];

            b[i]=b[i-];

            if(a[i])

                h[i]++;

            else

                b[i]++;

        }

        for(t=;t<=y;t++)

        {

            for(i=t;i<=x;i++)

                for(int j=t-;j<i;j++)

                dp[i][t]=min(dp[i][t],dp[j][t-]+(h[i]-h[j])*(b[i]-b[j]));

        }

        printf("%d\n",dp[x][y]);

    }

    return ;

}