#P2514. [HAOI2010] 工厂选址
[HAOI2010] 工厂选址
题目描述
某地区有 座煤矿,其中第 号矿每年产量为 吨。现有一火力发电厂,每年需用煤恰好 吨,每年运行的固定费用(不包括煤的运费)为 元,每吨原煤从第 号矿运到火力发电厂的运费为 元。
现规划新建一个发电厂, 座煤矿每年开采的原煤将全部供给这两座发电厂。有 个备选的新发电厂厂址,若在第 号备选厂址建新厂,每年运行的固定费用为 元;每吨原煤从第 号矿运到第 号备选厂址的运费为 元。
试问:应如何选取新厂厂址并分配 座煤矿开采的原煤,才能使每年的总费用(发电厂运行费用与原煤运费之和)最小。
输入格式
第一行四个整数 。
接下来一行 个整数 表示每一处煤矿的年产量。
接下来一行 个整数 表示新厂建在每一个位置的固定费用。
接下来 行每行 个正整数,第 行描述 的值。
输出格式
第一行一个整数表示选择的新发电厂的厂址编号,如有多个厂址满足条件,输出最小的一个;
第二行一个整数表示最小的年总费用。
4 2 7 9
3 1 10 3
6 3 7 1 10 2 7 4 9
1 2 4 3
6 6 8 2
4 10 8 4
10 2 9 2
7 6 6 2
9 3 7 1
2 1 6 9
3 1 10 9
4 2 1 8
2 1 3 4
8
49
提示
对于的数据,,,,,,,。