望大牛指点一下
查看状态 Show Status
状态题目:Orz细菌
题目编号:392-Orz细菌 查看该题
状态: Unaccepted
测评机： Xeond[6]
得分： 80分
提交日期： 2008-11-12 11:27:00
有效耗时： 2390毫秒
测试结果1: 通过本测试点|有效耗时156:ms
测试结果2: 通过本测试点|有效耗时187:ms
测试结果3: 通过本测试点|有效耗时172:ms
测试结果4: 测试结果错误.错误结果为:71921
正确结果应为:71890
测试结果5: 测试结果错误.错误结果为:165098
正确结果应为:165096
测试结果6: 通过本测试点|有效耗时234:ms
测试结果7: 通过本测试点|有效耗时281:ms
测试结果8: 通过本测试点|有效耗时406:ms
测试结果9: 通过本测试点|有效耗时485:ms
测试结果10: 通过本测试点|有效耗时469:ms
var
n,m,k,i,j,tot,a,summ,min,ins,p:longint；
d:array[0..100010] of longint；
b,c,sum:array[0..25] of longint；
f:array[0..25,0..25] of longint；
procedure up(y:longint)；
var
z:longint；
begin
if y=1 then exit；
if d[y div 2]>d[y] then
begin
z:=d[y]；d[y]:=d[y div 2]；d[y div 2]:=z；
up(y div 2)；
end；
end；
procedure down(y:longint)；
var
z:longint；
begin
if y*2>tot then exit；
if y*2+1>tot then
begin
if d[y]>d[y*2] then
begin
z:=d[y]；d[y]:=d[y*2]；d[y*2]:=z；
down(y*2)；
end；
end
else
begin
if (d[y*2]<d[y]) or (d[y*2+1]<d[y]) then
begin
if d[y*2]<d[y*2+1] then
begin
z:=d[y]；d[y]:=d[y*2]；d[y*2]:=z；
down(y*2)；
end
else
begin
z:=d[y]；d[y]:=d[y*2+1]；d[y*2+1]:=z；
down(y*2+1)；
end
end；
end；
end；
procedure insert(x:longint)；
begin
inc(tot)；
d[tot]:=x；
up(tot)；
end；
procedure del；
begin
d[1]:=d[tot]；
dec(tot)；
down(1)；
end；
procedure dp；//估计是里面错了。请大牛看看
var
i,j:longint；
begin
for i:=m+1 to 2*m do
c:=c[i-m]；
for i:=1 to 2*m do
for j:=1 to 2*m do f[i,j]:=999999999；
for i:=1 to 2*m do f[i,i]:=0；
for i:=1 to 2*m-1 do
f[i,i+1]:=c+c[i+1]；
sum[0]:=0；
for i:=1 to 2*m do
sum:=sum[i-1]+c；
for i:=2 to m-1 do
for j:=1 to 2*m do
begin
if i+j>2*m then break；
for k:=0 to i-1 do
if f[j,j+k]+f[j+k+1,i+j]+sum[i+j]-sum[j-1]<f[j,i+j] then
f[j,i+j]:=f[j,j+k]+f[j+k+1,i+j]+sum[i+j]-sum[j-1]；
end；
min:=999999999；
for i:=1 to m do
if f[i,i+m-1]<min then min:=f[i,i+m-1]；
end；
begin
assign(input,’ex3.in’)；reset(input)；
assign(output,’ex3.out’)；rewrite(output)；
readln(n,m,k)；
tot:=0；
for i:=1 to n do
begin
read(a)；
insert(a)；
end；
summ:=0；
for i:=1 to k do
begin
for j:=1 to m do
begin
b[j]:=d[1]；
del；
end；
for j:=1 to m do
begin
read(p)；
c[j]:=b[p]；
end；
dp；//石子归并
summ:=summ+min；
ins:=0；
for j:=1 to m do
inc(ins,b[j])；
insert(ins)；
end；
writeln(summ)；
close(input)；close(output)；
end.