2 shunfurh shunfurh 于 2017.09.04 13:57 提问

Against Mammoths

Problem Description
Back to year 3024, humans finally developed a new technology that enables them to conquer the alien races. The new technology made it possible to produce huge spaceships known as Saber Tooth spaceships as powerful as the aliens' defending mammoths. At that time, humans ruled several planets while some others were under control of the aliens. Using Saber Tooth ships, humans finally defeated aliens and this became the first Planet War in history. Our goal is to run a simulation of the ancient war to verify some historical hypotheses.

Producing each spaceship takes an amount of time which is constant for each planet but may vary among different planets. We call the number of spaceships each planet can produce in a year, the production rate of that planet. Note that each planet has a number of spaceships in it initially (before the simulation starts). The planets start producing ships when the simulation starts, so if a planet has nships initially, and has the production rate p, it will have n + p ships at the beginning of year 1, and n + i × p ships at the beginning of year i (years are started from zero).

Bradley Bennett, the commander in chief of the human armies, decided a strategy for the war. For each alien planet A, he chooses a corresponding human planet P, and produces spaceships in P until a certain moment at which he sends all spaceships in P to invade the planet A. No alien planet is invaded by two human planets and no human planet sends its spaceships to two different alien planets.

The defense power of the alien planets comes from their powerful mammoths. Each alien planet contains a number of mammoths initially and produces a number of mammoths each year (called the production rate of the planet). When a fight between spaceships and mammoths takes place, the side having the greater number of troops is the winner. If the spaceships win, the alien planet is defeated. In case the number of mammoths and spaceships are equal, the spaceships win.

The difficulty with planning this strategy is that it takes some time for the spaceships to reach the alien planets, and during this time, the aliens produce mammoths. The time required for spaceships to travel from each human planet to each alien planet is known. The ships can leave their planets only at the beginning of years (right after the ships are produced) and reach the alien planets at the beginning of years too (right after the mammoths are produced).

As an example, consider a human planet with two initial spaceships and production rate three invading an alien planet with two initial mammoths and production rate two. The time required to travel between the two planets is two years and the ships are ordered to leave at year one. In this case, five ships leave the human planet. When they reach the alien planet, they confront eight mammoths and will be defeated during the fight.

Bennett decided to prepare a plan that destroys every alien planet in the shortest possible time. Your task is to write a program to generate such a plan. The output is the shortest possible time (in years) in which every alien planet is defeated.

Input
There are multiple test cases in the input. The first line of each test case contains two numbers H and A which are the number of planets under the control of humans and aliens respectively (both between 1 and 250). The second line of the test case contains H non-negative integers n1 m1 n2 m2 … nH mH. The number ni is the initial number of Saber Tooth spaceships in the ith human planet and mi is the production rate of that planet. The third line contains A non-negative integers which specify the initial number of mammoths and the production rate of the alien planets in the same format as the second line. After the third line, there are H lines each containing A positive integers. The jth number on the ith line shows how many years it takes a spaceship to travel from the ith human planet to the jth alien planet. The last line of the input contains two zero numbers. Every number in the input except H and A is between 0 and 40000.

Output
The output for each test case contains a single integer which is the minimum time in which all alien planets can be defeated. If it is impossible to destroy all alien planets, the output should be IMPOSSIBLE.

Sample Input
2 1
2 3 0 3
2 2
2
2
0 0

Sample Output
6

2个回答

shen_wei
shen_wei   Ds   Rxr 2017.09.04 17:08
已采纳
caozhy
caozhy   Ds   Rxr 2017.09.05 00:11
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
POJ 3343 Against Mammoths
Against Mammoths Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 1676   Accepted: 542 Description Back to year 3024, humans finally developed a new technol
poj3343 Against Mammoths,二分图匹配
poj3343 二分图匹配 一道有(hen)趣(shui)的题目。 二分时间上界,可以将最优化问题变成判定性问题。 然后用二分图匹配判断是否每个星球都被匹配上就可以啦。 有几个trick:1.时间上界可能达到1600080000左右。 2.当人类星球初始值是0时,至少要1年时才能出发。 3.如果人类某星是0,0 ,外星人某星是0,0 也是不合法地。
HDU 2413 Against Mammoths
大意:地球人要占领喵星人的星球,给定地球战舰的初始值以及每年递增的速率,喵星人战舰初始值,以及每年递增的速率,求在一个最小的时间,在改时间内占领全部星球。(一个星球只能占领一个喵星球) 思路:由最后一个条件知道二分匹配,然后二分差值即可,WA了几次,开始以为是数据在0-40000之内,后来发现可能很大,而且精度转换会有误差。 #include #include #include #inc
poj 3343 Against Mammoths
题目超长,难在读题,理解题以后就可以看出是一道二分查找+最大匹配的题目了 题意:有n个人类星球,m个外星球,每个星球上开始sh艘飞船,之后每年会生产p艘飞船,人类想要战胜所有的外星球,每个人类星球和每个外星球的距离已知(需要耗费年),比如在a年初,人类星球H向外星球A宣战,那么人类会带上sh+p*a艘飞船进攻,经过k年后到达外星球,这时外星球飞船的数量为sh'+p'*(a+k),如果这时人类飞船
POJ 3343 Against Mammoths (二分匹配)
Description Back to year 3024, humans finally developed a new technology that enables them to conquer the alien races. The new technology made it possible to produce huge spaceships known as Saber
poj 3343 Against Mammoths 二分图最大匹配
题意:
HDU 2413 POJ 3343 Against Mammoths(二分图匹配)
题意:星球大战 ,地球人有n个星球,外星人有m个星球,每一个星球都初始的飞机数,和生产飞机的能力。问地球人要多长时间才能打败外星人。。 1,一个地球人的星球只能打一个外星人的星球,一个外星人的星球只能被一个地球人的星球攻击,因此可以用二分图匹配。(开始时没有看清这句,以为是线性规划的问题,老感觉不对劲,看了别人用二分图匹配之后,,,,) 2,二分时间。时间的最大值,我也不会算,() 用INF=
Mysql全文搜索match...against的用法 转自:http://dao.daimaku.com
前提:mysql只支持英文内容的全文索引,所以只考虑英文的全文搜索。假定数据表名为post,有三列:id、title、content。id是自增长序号,title是varchar,content是text,给content添加全文索引。 mysql全文搜索有三种模式:
Mysql利用match...against进行全文检索
在电商项目中,最核心的功能之一就是搜索功能,搜索做的好,整个电商平台就是个优秀的平台。一般搜索功能都使用搜索引擎如Lucene、solr、elasticsearch等,虽然这功能比较强大,但是对于一些小公司或者小的电商平台项目有点大材小用了,对于小项目我们可以采用折中的方法,使用ik+mysql的搜索引擎进行查询,ik用于分词,mysql利用match和against函数进行模糊查询。先写下mysql的match和against的用法。
relocation R_X86_64_32S against -fPIC
/usr/bin/ld: src/common/common.o: relocation R_X86_64_32S against `.data' can not be used when making a shared object; recompile with -fPIC src/common/common.o: error adding symbols: Bad value colle