1 (azaleas) 7 23 -5 -24 16 Bunches 2 (begonias) 5 21 -4 10 23 3 (carnations) -21 5 -4 -20 20 According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.
To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.
ASSUMPTIONS
1 <= F <= 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.
F <= V <= 100 where V is the number of vases.
-50 <= Aij <= 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j.
INPUT
The input is a text file named flower.inp. The first line contains two numbers: F, V.
The following F lines: Each of these lines contains V integers, so that Aij is given as the jth number on the (i+1)st line of the input file.
OUTPUT
The output must be a text file named flower.out consisting of two lines: The first line will contain the sum of aesthetic values for your arrangement. The second line must present the arrangement as a list of F numbers, so that the k’th number on this line identifies the vase in which the bunch k is put.
EXAMPLE
flower.inp: 3 5
7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20
flower.out: 53 2 4 5
EVALUATION
Your program will be allowed to run 2 seconds.
No partial credit can be obtained for a test case.
第 16 页 共 29页
2. “钉子与小球”试题
有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
in我们知道小球落在第i个格子中的概率pi?Cn2?n!i!(n?i)!n其中i为格子2，
的编号，从左至右依次为0,1,...,n。
现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。
图1??????????????? ??????????图2?????????? ???????????????图3
输入
第1行为整数n（2<=n<=50）和m（0<=m<=n）。
以下n行依次为木板上从上至下n行钉子的信息，每行中‘*’表示钉子还在，‘.’?表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。
输出
仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概率pm。 既约分数的定义：A/B是既约分数，当且仅当A、B为正整数且A和B没有大于1的公因子。
样例输入 5 2 * * . * * * * . * * * * * * *
样例输出 7/16
3. 例2“花店橱窗布置问题”方法1的源程序
第 17 页 共 29页
program IOI99_LittleShopOfFlowers;
var F,V :byte; {花束和花瓶的数目} A :array [1..100,1..100] of shortint; {A[i,j]花束i放在花瓶j中的美学值} Best :array [0..100,0..100] of integer;
{Best[i,j]前i束花放在前j个花瓶中的最优解}
{Previous[i,j]在Best[i,j]的最优解中，花束i-1的位置} Previous :array [1..100,1..100] of byte;
procedure ReadIn; {读入} var i,j :byte; begin reset(input);
readln(F,V);
for i:=1 to F do begin for j:=1 to V do read(A[i,j]);
readln; end;
close(input); end;
procedure Work; {规划主过程} var i,j,t
:byte;
begin fillchar(Best[0],sizeof(Best[0]),0); {边界条件} for i:=1 to F do
for j:=i to V+i-F do begin
Best[i,j]:=low(Best[i,j]); for t:=i-1 to j-1 do {枚举花束i-1的位置}
if Best[i-1,t]>Best[i,j] then begin {更新当前最优解}
Best[i,j]:=Best[i-1,t]; Previous[i,j]:=t; end;
inc(Best[i,j],A[i,j]);
end;
end;
procedure Print; {打印最优解}
第 18 页 共 29页
var
i,j :byte; Put :array [1..100] of byte; begin i:=F;
begin assign(input,'flower.inp'); assign(output,'flower.out'); ReadIn;
Work; Print;
for j:=F+1 to V do {选择全局最优解}
if Best[F,j]>Best[F,i] then i:=j; {i最后一束花的位置} rewrite(output); writeln(Best[F,i]); for j:=F downto 1 do begin
Put[j]:=i;
i:=Previous[j,i];
end;
for i:=1 to F do write(Put[i],' '); writeln;
close(output);
end;
end.
4. 例2“花店橱窗布置问题”方法2的源程序
program IOI99_LittleShopOfFlowers; var F,V :byte; {花束和花瓶的数目}
A :array [1..100,1..100] of shortint; {A[i,j]花束i放在花瓶j中的美学值} Best :array [0..100,0..100] of integer; {Best[i,j]前i束花放在前j个花瓶中的最优解} Choice :array [0..100,0..100] of boolean; {Choice[i,j] 花束i是否放在花瓶j中}
{读入}
procedure ReadIn; var
i,j :byte; reset(input); readln(F,V); begin
第 19 页 共 29页
for i:=1 to F do begin for j:=1 to V do read(A[i,j]); readln; end;
close(input);
end;
procedure Work; {规划主过程} var i,j :byte;
begin fillchar(Best[0],sizeof(Best[0]),0); {边界条件}
for i:=1 to F do begin
Best[i,i]:=Best[i-1,i-1]+A[i,i]; {唯一的选择} Choice[i,i]:=true;
for j:=i+1 to V+i-F do begin
Choice[i,j]:=Best[i-1,j-1]+A[i,j]>Best[i,j-1]; if Choice[i,j] then Best[i,j]:=Best[i-1,j-1]+A[i,j] {i放在j中} else Best[i,j]:=Best[i,j-1]; {i不放在j中} end;
end; end;
procedure Print; {打印最优解} var
i,j :byte;
Put :array [1..100] of byte; {Put[i]花束i所在的花瓶}
begin rewrite(output);
writeln(Best[F,V]); i:=F;
for j:=V downto 1 do {倒推求Put}
if Choice[i,j] then begin
Put[i]:=j; dec(i);
end;
for i:=1 to F do begin
第 20 页 共 29页