codevs 1962 马棚问题--序列型DP

1962 马棚问题

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

6 3

样例输出 Sample Output

/*典型的序列性DP，f[i][j]记录前i匹马，分到j个马棚里的最小不愉快系数,p[i][j]储存着i到j这个区间的马在一个马棚里的不愉快系数,house[i]储存着到地i匹马总共有多少匹白马，多少匹黑马*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

using namespace std;

#define N 501

int f[N][N],p[N][N];

struct House{

    int a;int b;

};

House house[N];

int n,k;

void input()

{

    scanf("%d%d",&n,&k);

    int x;

    for(int i=;i<=n;++i)

    {

        scanf("%d",&x);

        house[i].a=house[i-].a;

        house[i].b=house[i-].b;

        if(x==) house[i].a++;

        if(x==) house[i].b++;

    }

    for(int i=;i<=n-;++i)/*对于p数组的预处理特别重要*/

      for(int j=i+;j<=n;++j)

      {

          int r1=abs(house[i-].a-house[j].a);

          int r2=abs(house[i-].b-house[j].b);

          p[i][j]=r1*r2;

      }

    memset(f,,sizeof(f));

    for(int i=;i<=n;++i)

    f[i][]=p[][i];/*DP方程的边界，前i个马在一个马棚的不愉快系数*/

}

void dp()

{

    for(int j=;j<=k;++j)

      for(int i=j;i<=n;++i)

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

        f[i][j]=min(f[i][j],f[t][j-]+p[t+][i]);/*DP方程前i匹马，分到j个马棚里的最小不愉快系数，就是把j-1<=t<=i-1匹马放到j-1个马棚中，其余t+1到i匹马在一个马棚中的不愉快系数最小值*/

}

int main()

{

    input();

    dp();

    cout<<f[n][k]<<endl;

    return ;

}