2097. least Shots

单点时限: 2.0 sec

内存限制: 256 MB

The KiloMan series has always had a consistent pattern: you start off with one (rather weak) default weapon, and then defeat some number of bosses. When you defeat a boss, you then acquire his weapon, which can then be used against other bosses, and so on. Usually, each boss is weak against some weapon acquired from another boss, so there is a recommended order in which to tackle the bosses. You have been playing for a while and wonder exactly how efficient you can get at playing the game. Your metric for efficiency is the total number of weapon shots fired to defeat all of the bosses.

You have a chart in front of you detailing how much damage each weapon does to each boss per shot, and you know how much health each boss has. When a boss’s health is reduced to 0 or less, he is defeated. You start off only with the Kilo Buster, which does 1 damage per shot to any boss. The chart is represented as a String[], with the ith element containing N one-digit numbers (‘0’-‘9’), detailing the damage done to bosses 0, 1, 2, …, N-1 by the weapon obtained from boss i, and the health is represented as a int[], with the ith element representing the amount of health that boss i has.

输入格式

There are many test cases.Each test case given a n then n*n characters of damageChart representing all the weapon damages, and then n interger showing how much health each boss has.

-damageChart will contain between 1 and 15 elements, inclusive.

-each element of damageChart will be of the same length, which will be the same as the number of elements in damageChart.

-each element of damageChart will contain only the characters ‘0’-‘9’.

-bossHealth will contain between 1 and 15 elements, inclusive.

-damageChart and bossHealth will contain the same number of elements.

-each element in bossHealth will be between 1 and 1000000, inclusive.

输出格式

your output an int which is the least number of shots that need to be fired to defeat all of the bosses.

样例

Input
4
1542
7935
1139
8882
150 150 150 150
Output
205
Defeat boss 2, use his weapon to defeat boss 3, and then use boss 3's weapon to defeat both bosses 0 and 1, for a total shot count of 150 + 17 + 19 + 19 = 205. It would be more efficient to defeat boss 1 with his own weapon, but it would be cheating to get his weapon before defeating him.

2 人解决,4 人已尝试。

2 份提交通过,共有 8 份提交。

9.1 EMB 奖励。

创建: 12 年,6 月前.

修改: 3 年,1 月前.

最后提交: 9 年,9 月前.

来源: TC

题目标签