双色马

题目：http://www.razxhoi.com/mod/programming/view.php?id=5419
【题目描述】双色马（Binhorse.cpp/c/pas）URAL 1167

邪狼负责管理所有的战马，每天，他放出所有战马，任它们奔跑嬉戏。到了晚上，邪狼把所有马带回马厩，邪狼把它们排在一条直线上然后跟着他回厩。由于马儿们很累，邪狼尽量不让它们移动。所以他发明了一个算法：他把前P1匹马放在第一个马厩，下面P2只马放在第二个马厩，等等，而且，他不想K个马厩任何一个是空的，并且没有马被留在外边。邪狼有黑白两种颜色的马，两种颜色的马相处不好。如果有i匹黑马和j匹白马同在一个马厩中，那么这个马厩的忧愁系数为i×j。总忧愁系数是所有马厩忧愁系数的和。恢愁系数过大会表现在马儿互相打架或者马儿彻夜长嘶，这会引起修罗王的不满，邪狼可能要被惩罚，后果您也可以想象出来，很严重的！故请决定一种方法把N匹马放进K个马厩使得总忧愁系数最小。

【输入格式】
第一行是N（1≤N≤500）和K（1≤K≤N），下面N行有N个数第i行是第i只马的颜色，1代表黑色，0代表白色。

【输出格式】
最小的总忧愁系数。

【输入样例】
6 3
1
1
0
1
0
1
【输出样例】
2

【样例说明】
将前2匹马放在第一个马厩，下面3匹马放在第二个马厩，最后一匹马放在第三个马厩。

【时间限制】
1秒

【内存限制】
16MB

题解：这是一道经典的动态规划问题，我们可以用dp[i][l]来表示前i匹马放进l个马厩，由于只有两种马，可以用sum[i]表示前i匹马有多少匹黑色的，白色的就是i-sum[i]个，j表示从l-1到i-1中马的摆放位置，则zhea转移方程dp[i][l]=min(dp[i][l],dp[j][l-1]+(j+1到i的黑马数*j+1到i的白马数）。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,k,a[505],sum[505],dp[505][505],b[505][505];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    freopen("Binhorse.in","r",stdin);
    freopen("Binhorse.out","w",stdout);
    int i,j,l;
    cin>>n>>k;
    memset(dp,127/3,sizeof(dp));
    for(i=1; i<=n; i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];//一个时手动求
        dp[i][1]=sum[i]*(i-sum[i]);
    }

    for(l=2; l<=k; l++)
    {
        for(i=l; i<=n; i++)
        {
            for(j=l-1; j<i; j++)
            {
                dp[i][l]=min(dp[i][l],dp[j][l-1]+(sum[i]-sum[j])*(i-j-sum[i]+sum[j]));//白马数为j+1到i的个数-黑马数。
            }
        }
    }
    cout<<dp[n][k]<<endl;
    return 0;
}