每天，小明和他的马外出，然后他们一边跑一边玩耍。当他们结束的时候，必须带所有的马返回马棚，小明有K个马棚。他把他的马排成一排然后跟随它走向马棚，因为他们非常疲劳，小明不想让他的马做过多的移动。因此他想了一个办法：将马按照顺序放在马棚中，后面的马放的马棚的序号不会大于前面的马放的马棚的序号。而且，他不想他的K个马棚中任何一个空置，也不想任何一匹马在外面。已知共有黑、白两种马，而且它们相处得并不十分融洽。如果有i个白马和j个黑马在一个马棚中，那么这个马棚的不愉快系数将是i*j。所有k个马棚不愉快系数的和就是系数总和。确定一种方法把n匹马放入k个马棚，使得系数总和最小
input：
输入：在第一行有两个数字：n（1≤n≤500）和k（1≤k≤n）。在接下来的n行是n个数。在这些行中的第i行代表队列中的第i匹马的颜色：1意味着马是黑色的，0意味着马是白色的
output：
输出：只输出一个单一的数字，代表系数总和可能达到的最小值
input：
6 3 {6匹马，3个马棚}
1 {第1匹马为黑马}
1
0 {第3匹马为白马}
1
0
1
output：
2
分析：
本题是典型的DP，对于n匹马，m个马棚。状态分析：F[i][j]表示前i匹马在j个马棚的最优值；s[i][j]表示i到j匹马的最优值。在依次枚举k个马棚的位置找出最优，则有状态方程：f[i][k]=min(f[j][k],f[j][k-1]+s[j+1][i])<0<i<n+1,0<j<n+1,0<k<m+1>
【参考程序】：
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
long find_min(long x,long y)
{
if (x<y) return x;
else return y;
}
int main()
{
long n,m,i,j,k,x;
scanf("%d%d",&n,&m);
long f[n+1][m+1],s[n+1][n+1],a[n+1];
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++) f[i][j]=9999999;
scanf("%d",&a[i]);
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
x=0;
for (k=i;k<=j;k++) x+=a[k];
s[i][j]=x*(j-i+1-x);
}
for (i=1;i<=n;i++) f[i][1]=s[1][i];
for (k=2;k<=m;k++)
for (i=k+1;i<=n;i++)
for (j=k-1;j<=n;j++)
f[i][k]=find_min(f[i][k],f[j][k-1]+s[j+1][i]);
printf("%d\n",f[n][m]);
system("pause");
return 0;
}