var a:array[0..600] of longint；
f,w:array[0..600,0..600] of longint；
x,i,j,k,m,n,z,y,u,v,s,t:longint；
f1,f2:text；
function min(a,b:longint):longint；
begin
min:=a；
if min>b then min:= b；
end；
procedure init；
begin
assign(f1,’zin.in’)；
reset(f1)；
read(f1,n,m)；
for i:= 1 to n do
read(f1,a[i])；
close(f1)；
end；
procedure first；
begin
for i:= 1 to n-1 do
for j:= i+1 to n do
begin
for k:= i to j do
if a[k]=1 then inc(x)
else inc(y)；
f[i,j]:= x*y； x:=0； y:=0；
end；
for i:= 1 to n do
for j:= 1 to m do
w[i,j]:=maxlongint；
end；
procedure doit；
begin
for i:= 1 to n do
w[i,1]:=f[1,i]；
for i:= 2 to m do
for j:= i to n do
for k:= i-1 to j-1 do
w[j,i]:=min(w[j,i],w[k,i-1]+f[k+1,j])；
end；
procedure outit；
begin
assign(f2,’zout.out’)；
rewrite(f2)；
write(f2,w[n,m])；
close(f2)；
end；
begin
init；
first；
doit；
outit；
end.
我的程序... 感觉有点像.. 乘积最大..
{把一个长N的数列等分为M分的问题}(该句为应用的)
{{顺便.. 提交100次 纪念下..}与本话题无关}
p,f:array[1..550,1..550] of longint；
m,k,n,i,j,x,y:longint；
begin
read(m,k)；
for i:=1 to m do read(a[i])；
for i:=1 to m do
for j:=i to m do begin
x:=0；y:=0；
for n:=i to j do
if a[n]=0 then inc(x)
else inc(y)；
p[i,j]:=x*y；
end；
for i:=2 to k do
for j:=1 to m do
f[j,i]:=maxint；
for i:=1 to m-k+1 do
f[i,1]:=p[1,i]；
for i:=2 to k+1 do
for j:=i-1 to m-k+i-1 do
for x:=m-k+i downto j+1 do
if f[x,i]>=f[j,i-1]+p[j+1,x] then
f[x,i]:=f[j,i-1]+p[j+1,x]；
write(f[m,k])；
end.
var
a,b:array[0..500] of integer；
mm:array[1..500,1..500] of longint；
i,j,k,l,m,n,ff:longint；
procedure init；
begin
readln(n,m)；
fillchar(a,sizeof(a),0)；
fillchar(b,sizeof(b),0)；
fillchar(mm,sizeof(mm),0)；
for i:=1 to n do
begin
readln(ff)；
a[i]:=a[i-1]；
b[i]:=b[i-1]；
if ff=1 then inc(a[i]) else inc(b[i])；
end；
end；
procedure main；
begin
for i:=1 to n-m+1 do
mm[1,i]:=a[i]*b[i]；
for i:=2 to m do
for j:=i to n-(m-i) do
begin
mm[i,j]:=maxlongint；
for l:=i-1 to j-1 do
begin
ff:=(a[j]-a[l])*(b[j]-b[l])；
if mm[i,j]>mm[i-1,l]+ff then mm[i,j]:=mm[i-1,l]+ff；
end；
end；
end；
begin
init；
main；
writeln(mm[m,n])；
end.
首先我不是牛。。。。
这道题的转移规则是：前i个马厩进j个马时的最小。(求的时候i前面的情况枚举)
应该是很清楚了吧，自己想通最后一点效果应该更好。
程序仅供参考