花店橱窗布置

基础算法,noip,noi,解题报告,搜索,动态规划,贪心,分治,数据结构

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

你想将你的花店的橱窗以一个最好的形态来布置。你现有F束花, 每束花都是不同种类的。同时, 橱窗上最少会有与花束数目相同的花瓶。这些花瓶是固定在橱窗的一个架上, 并且以相连的数目字由1至V将之加以编号。其中V为花瓶的数目。编号方式是由左至右, 即最左的一个花瓶编号为1而最右一个编号为V。而花束则可以在花瓶间搬动, 花束并以整数1至F加以编号。这些花束的编号, 是有一定的意义 : 就是这些编号决定花束在一行花瓶之间放置的次序, 即若i < j , 则花束i必定要放置在一个放有花束j的花瓶的左方的花瓶内。例如, 若你有一束Azaleas花(其编号为1), 一束Begonias花(其编号为2)及一束 Carnations花(其编号为3)。则所有的花束必定要以保持其编号顺序的形式放置放入花瓶内。即Azaleas花束必须要放在放有Begonias花束的花瓶的左方的一个花瓶内, 且Begonias花束亦要放在一个放有Carnations花束的花瓶的左方的一个瓶内。若花瓶的数目比花束的数目为多时, 多余的花瓶将会被空置, 每个花瓶只可以放有一束花。

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

花店橱窗布置

根据以上之列表, 其中如 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个数

Word文档免费下载Word文档免费下载:花店橱窗布置 (共3页,当前第1页)

花店橱窗布置相关文档

最新文档

返回顶部