p1269 马棚
题目：
每天，小明和他的马外出，然后他们一边跑一边玩耍。当他们结束的时候，必须带所有的马返回马棚，小明有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
1
1
0
1
0
1
{6匹马，3个马棚}
{第1匹马为黑马}
{第3匹马为白马}
输出：只输出一个单一的数字，代表系数总和可能达到的最小值
2 {最小系数总和}
这道题我是先直接求出从牧场i到j的不愉快值，然后再用DP状态转移f[i][j]=min(f[i][j],f[i-1][k]+b[k+1][j]);然后输出f[k][n]就好了
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
int a[];
int f[][];
int b[][];
int main()
{
int n,k;
cin>>n>>k;
memset(f,,sizeof(f));
for(int i=;i<=n;i++)
cin>>a[i];
int bl,w;
for(int i=;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
bl=;w=;
for(int k=i;k<=j;k++)
{
if(a[k]==)
{
bl++;
}
if(a[k]==)
{
w++;
}
}
b[i][j]=bl*w;
}
}
for(int i=;i<=n;i++)
{
f[][i]=b[][i];
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<f[i][j]<<' ';
}
cout<<endl;
}*/
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
for(int k=;k<=j;k++)
{
f[i][j]=min(f[i][j],f[i-][k]+b[k+][j]);
}
}
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<f[i][j]<<' ';
}
cout<<endl;
}*/
cout<<f[k][n]<<endl;
return ;
}