const
maxm=99999999；
var
i,j,k,n:longint；
b,w:array[0..510]of longint；
ff:array[0..510,0..510]of longint；
function dfs(dep,m:longint):longint；
var
i,x,p,tmp:longint；
begin
if (dep>=0)and(m<=0)then exit(maxm)；
if ff[dep,m]<>-1 then exit(ff[dep,m])；
tmp:=maxm；
for i:=1 to m-(dep-1) do
begin
p:=dfs(dep-1,m-i)；
if tmp>p then
begin
tmp:=p；
x:=i；
end；
end；
ff[dep,m]:=tmp+(b[m]-b[m-x])*(w[m]-w[m-x])；
exit(ff[dep,m])；
end；
begin
b[0]:=0；
w[0]:=0；
readln(n,k)；
if n=k then begin writeln(0)； exit； end；
for i:=0 to n do
for j:=0 to n do
ff[i,j]:=-1；
for i:=1 to n do
begin
readln(j)；
if j=0 then
begin w[i]:=w[i-1]+1； b[i]:=b[i-1]； end
else
begin w[i]:=w[i-1]； b[i]:=b[i-1]+1； end；
end；
for i:=1 to n do
ff[1,i]:=w[i]*b[i]；
writeln(dfs(k,n))；
end.
记忆化搜索只能得30分....
实在不知道哪里错了...请大牛赐教，谢谢
program horse；
const
maxm=99999999；
var
i,j,k,n:longint；
b,w:array[0..510]of longint；
ff:array[0..510,0..510]of longint；
function dfs(dep,m:longint):longint；
var
i,p,tmp:longint；
begin
if (dep>=0)and(m<=0)then exit(maxm)；
if ff[dep,m]<>-1 then exit(ff[dep,m])；
tmp:=maxm；
for i:=1 to m-(dep-1) do
begin
p:=dfs(dep-1,m-i)+(w[m]-w[m-i])*(b[m]-b[m-i])； // 这样才能记录当前的值，上面的那个错误的代码记录的不是当前值；
if tmp>p then tmp:=p；
end；
ff[dep,m]:=tmp；
exit(ff[dep,m])；
end；
begin
b[0]:=0；
w[0]:=0；
readln(n,k)；
if n=k then begin writeln(0)； exit； end；
for i:=0 to n do
for j:=0 to n do
ff[i,j]:=-1；
for i:=1 to n do
begin
readln(j)；
if j=0 then
begin w[i]:=w[i-1]+1； b[i]:=b[i-1]； end
else
begin w[i]:=w[i-1]； b[i]:=b[i-1]+1； end；
end；
for i:=1 to n do
ff[1,i]:=w[i]*b[i]；
writeln(dfs(k,n))；
end.
题目编号:273-马棚问题 查看该题
状态: Accepted
测评机： Xeost[5]
得分： 100分
提交日期： 2009-11-5 11:24:00
有效耗时： 1424毫秒
测试结果1: 通过本测试点|有效耗时313ms
测试结果2: 通过本测试点|有效耗时46ms
测试结果3: 通过本测试点|有效耗时266ms
测试结果4: 通过本测试点|有效耗时172ms
测试结果5: 通过本测试点|有效耗时62ms
测试结果6: 通过本测试点|有效耗时47ms
测试结果7: 通过本测试点|有效耗时47ms
测试结果8: 通过本测试点|有效耗时204ms
测试结果9: 通过本测试点|有效耗时204ms
测试结果10: 通过本测试点|有效耗时63ms