花店橱窗布置

回专题模式回学习阶段模式【题目名称、来源】花店橱窗布置 ioi99-1 【问题描述】

你想将你的花店的橱窗以一个最好的形态来布置。你现有F束花, 每束花都是不同种类的。同时, 橱窗上最少会有与花束数目相同的花瓶。这些花瓶是固定在橱窗的一个架上, 并且以相连的数目字由1至V将之加以编号。其中V为花瓶的数目。编号方式是由左至右, 即最左的一个花瓶编号为1而最右一个编号为V。而花束则可以在花瓶间搬动, 花束并以整数1至F加以编号。这些花束的编号, 是有一定的意义 : 就是这些编号决定花束在一行花瓶之间放置的次序, 即若i

和花束一样, 每个花瓶都有自己的特色。因此, 将某束花放入某一个花瓶将会得到一个可观赏值(美感)。此值以一个整数表示之。这些观赏值是以以下的表列来表示。当一个花瓶是空置时, 其观赏值为零。

根据以上之列表, 其中如 Azaleas 花束, 若将之放入 2 号花瓶将会十分好看, 但若将之放入 4 号花瓶则会相当难看.

为了要得到最佳的视觉效果, 你将要设法找到观赏值总和为最高, 同时亦要保持花束顺序的排列的放置花束方法。若有多种排列方法都可以得到最高值时, 则任取其一作为输出即可。

假设

 1  F  100, 其中F为花束的数目, 花束的编号为1至F。  F  V  100, 其中V为花瓶的数目。

 -50  Aij  50, 其中 Aij 代表将花束i放入花瓶j时所得到的观赏值。

输入

输入为一个名为 flower.inp 的文字文件。  第一行中有两个数字: F, V

 随后有F行, 每行中包括V个整数, 即Aij的值是放于输入档的第(i+1)行中的第j个数

字。

输出

输出必为一个名为 flower.out 的文字文件, 文件内要有两行:

 第一行中有一个数字。它代表由你的放置方法所获得最大的观赏值的总和

 第二行代表花束放置的方法, 这方法是以一个由F个数字的排列所组成, 其中这行中第

K个数字代表编号为K的花束所放入的花瓶编号。

例子

评分

你的程序会有2秒的执行时间。这个题目将不会给局部分数。

【所属专题】动态规划

【适合学习阶段】第二阶段【解题思路】问题分析：方法1：

因为花束的排列顺序不能改变，所以对于编号为i的花瓶和编号j的花来说，设c[i,j]表示从1..i的花瓶中，放j束花的最大观赏值。按照花瓶编号划分阶段，则状态转移方程为

C[i,j]=0 当j>i

max{c[i-1,j] 当i瓶不放j花束，C[i-1,j-1]+hua[j，i],k>=j当i瓶放j花束}

方法2：

设c[i,j]代表方i束花到1..j编号的瓶子中的最大观赏值，即按照花的编号来划分阶段，则状态转移方程为

C[i,j]=0 当j

max{c[i,j-1] 当i花不放到j瓶里，c[i-1,j-1]+hua[i,j]当i花放到j瓶里}

存储结构：

【测试数据】

【源程序】