讨论 / 处女题解
crane 2011-11-08 16:26:00
点我顶贴 收藏 删除
VAR

i,j,k,m,n,f,v,t:longint;

a:array[1..100,1..100]of longint;//原始数据

d:array[0..100,0..100]of longint;//动归数组,本来想用 f 的,结果题目花朵数用了

p:array[1..100]of longint;//用来记录第 i 个花瓶中插哪朵花

BEGIN

assign(input,'496.txt'); reset(input);//我在本地测试用

readln(f,v);//花朵数,花瓶数

for i:=1 to f do

for j:=1 to v do read(a[i,j]);//读入原始数据

for i:=1 to f do//先考虑前几朵花

for j:=1 to v do//再考虑前几个花瓶

if j<i then continue else//明显没法插嘛

if i=j then d[i,j]:=d[i-1,j-1]+a[i,j]//明显必须插啊

else if d[i,j-1]>d[i-1,j-1]+a[i,j] then d[i,j]:=d[i,j-1]

else d[i,j]:=d[i-1,j-1]+a[i,j];//考虑第 i 朵花插不插

writeln(d[f,v]);//前 f 朵花 插前 v 个花瓶中的 最优

i:=f; j:=v; t:=0;// i 表示第几朵花, j 表示第几个花瓶

while (i>0)and(j>0) do

begin

if d[i,j]<>d[i,j-1] then//明显第 i 朵花插到了 第 j 个花瓶中

begin

inc(t);

p[t]:=j;//记录一下

dec(i);//减少花束一朵

end;

dec(j);//查看前一个花瓶是否有花

end;

for i:=v downto 2 do

if p[i]<>0 then//花瓶不是空

write(p[i],' ');

writeln(p[1]);

END.

查看更多回复
提交回复