|
石子合并
在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20).
(!)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小;
(2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小;
输入数据:
第一行为石子堆数N;
第二行为每堆的石子数,每两个数之间用一个空格分隔.
输出数据:
从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示.
输入输出范例:
输入:
4
4
5 9
4
输出:
－４
５
９ －４
－８
－５ ９
－１３
－９
２２
４
－５
－９
４
４
－１４
－４
－４
－１８
２２
最小代价子母树
设有一排数，共ｎ个，例如：22
14 7
13 26 15 11.任意2个相邻的数可以进行归并,归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小.
输入、输出数据格式与“石子合并”相同。
输入样例：
4
12
5 16
4
输出样例：
－１２
－５
１６
４
１７
－１６
－４
－１７
－２０
３７
背包问题
设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为ＸＫ，今从ｎ种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于ＸＫ，而价值的和为最大。
输入数据：
第一行两个数：物品总数Ｎ，背包载重量ＸＫ；两个数用空格分隔；
第二行N个数,为Ｎ种物品重量；两个数用空格分隔；
第三行N个数,为N种物品价值;
两个数用空格分隔；
输出数据：
第一行总价值；
以下N行，每行两个数，分别为选取物品的编号及数量；
输入样例：
4
10
2
3 4 7
1
3 5 9
输出样例：
12
2
1
4
1
商店购物
某商店中每种商品都有一个价格。例如，一朵花的价格是2
ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5
ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是10
ICU不是12
ICU。
编一个程序，计算某个顾客所购商品应付的费用。
要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，
即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，
并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14
ICU因为:
1朵花加2个花瓶:
优惠价:10 ICU
2朵花
正常价: 4 ICU
输入数据
用两个文件表示输入数据。第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF
ER．TXT）。
两个文件中都只用整数。
第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P
是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。
第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9
9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9
99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤
P≤9999）代表此商品组合的优惠价。当然，
优惠价要低于该组合中商品正常价之总和。
输出数据
在输出文件OUTPUT．TXT中写
一个数字（占一行）， 该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。
输入/输出数据举例
┌────────┐
┌────────────┐┌────────┐
│
INPUT │
│ OFFER．TXT ││
OUTPUＴ．TXT│
├────────┤
├────────────┤├────────┤
│
2 │
│ 2 ││
14 │
│ ７
３ ２
│ │
1 7 3 5 ││ │
│ ８
２ ５
│ │
2 7 1 8 2 10
││ │
└────────┘
└────────────┘└────────┘
|