DP——马棚问题

Description

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

Input

多个测试组，每组测试第一行有2个数字：n( 1 <= n <= 500)和k( 1 <= k <= n). 接下来的n行是n个数，在这些行中的第i行代表队列中的第i匹马的颜色：1意味着马是黑色的，0则是白色的。处理到结束。

Output

对每组测试数据输出一行，只输出一个数字，代表系数总和可能达到的最小值

Sample Input

Sample Output

HINT

大意：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 600,inf = 0x3f3f3f3f;
int a[MAX],b[MAX],w[MAX],dp[MAX][MAX];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n;i++)
        scanf("%d",&a[i]);
    for(int i = 1; i <= n;i++)
        for(int j = 1; j <= k; j++)
         dp[i][j] = inf;
    memset(b,0,sizeof(b));
    memset(w,0,sizeof(w));
    for(int i = 1 ;i <= n;i++){
        if(a[i] == 0){
            w[i] = w[i-1] + 1;
            b[i] = b[i-1];
        }
        else {
            b[i] = b[i-1] + 1;
            w[i] = w[i-1];
        }
        dp[i][1] = b[i]*w[i];
    }
    for(int i = 2; i <= k;i++){
        for(int j = i; j <=n;j++){
            for(int p = i-1;p < j;p++){
                int t1 = w[j] - w[p];
                int t2 = b[j] - b[p];
                dp[j][i] = min(dp[j][i],dp[p][i-1]+t1*t2);
            }
        }
    }
    printf("%d",dp[n][k]);
    return 0;
}

View Code