byvoid魔獸世界邀請(qǐng)賽-noip2011模擬賽4

1、BYVoid魔獸世界邀請(qǐng)賽NOIP2011模擬賽v（搜索與DP）之血精靈娜迦專場(chǎng)測(cè)試時(shí)間：測(cè)試時(shí)間：3小時(shí)小時(shí)【題目一覽】題號(hào)第一題第二題第三題第四題題目名稱尋找尤迪安橫渡法斯琪條件巴爾澤那被證實(shí)的預(yù)言提交文件find.pasccppthrough.pasccppcondition.pasccppsyndicate.pascpp輸入文件find.inthrough.incondition.insyndicate.in輸出文件find.o

2、utthrough.outcondition.outsyndicate.out時(shí)間限制1s1s1s1s空間限制64MB64MB64MB64MB分值100100100100尋找尤迪安【問(wèn)題描述】“阿爾薩斯王子在那刺向寒冰之冠的輝煌的那一劍，也就注定了他數(shù)年后的消亡。”——麥迪文手記之守護(hù)者的預(yù)言在諾德森一役中，幸存下來(lái)的血精靈王凱爾得知他忠效的主人—惡魔獵手尤迪安沒(méi)有死在霜之哀傷之下，而是被之前耐奧祖分流出來(lái)的力量所困??！這是一個(gè)重要的消

3、息。但是，耐奧祖的力量形成了一個(gè)龐大的磁場(chǎng)矩陣，而在這個(gè)磁場(chǎng)內(nèi)行走需要魔法，這對(duì)魔法充滿渴望的血精靈來(lái)說(shuō)是一個(gè)噩夢(mèng)，但是必須找到主人！血精靈們發(fā)現(xiàn)，這個(gè)矩陣內(nèi)有許多能量溢出點(diǎn)，他們可以用這些溢出的能量來(lái)補(bǔ)充魔法。能量溢出點(diǎn)的能量用完后，則變?yōu)槠降亍Ｄ憔褪莿P爾，你需要在磁場(chǎng)矩陣中走最少的步數(shù)來(lái)救你的主人，當(dāng)然，聰明的你會(huì)使用最少的魔法的?！据斎敫袷健康谝恍袨橐粋€(gè)整數(shù)N，表示一個(gè)NN的矩陣。（N50）接下來(lái)N1行為矩陣的描述，其中‘0’為空

4、地，‘1’為磁場(chǎng)，不可通行，‘3’為能量溢出點(diǎn)。接下來(lái)一行，為兩個(gè)整數(shù)A，B，表示凱爾的魔法初始值和每個(gè)能量溢出點(diǎn)能補(bǔ)充的魔法。提示（凱爾初始位置默認(rèn)為（11），尤迪安的默認(rèn)位置為（N，N））【輸出格式】輸出文件為兩行，第一行為最少步數(shù)，第二行為最少使用魔法值。（由于劇情需要，數(shù)據(jù)不提供無(wú)解）?！据斎胼敵鰳永枯斎耄?00003010001103001110條件巴爾澤那【問(wèn)題背景】你成功的消滅了洛倫丹邊境的亡靈軍隊(duì)。但是細(xì)心的法斯琪女士

5、發(fā)現(xiàn)，他們的力量似乎不來(lái)自于巫妖王阿爾薩斯。而且缺失了重要的成員亡靈巫師。那是巫妖克爾德加蘇的信徒們。似乎在洛倫丹，亡靈的統(tǒng)治發(fā)生了巨變。翌日，法斯琪的想法得到了證實(shí)。洛倫丹亡靈新的統(tǒng)治者之一，恐懼魔王巴爾澤那找上了尤迪安。原來(lái)，在阿爾薩斯王子的諾德森之戰(zhàn)中，巴爾澤那與追風(fēng)者西瓦娜動(dòng)了政變，攻占了洛倫丹人類人類聯(lián)盟的首都并殺死了原先的統(tǒng)治者恐懼魔王德拉瑞克特與聯(lián)盟首腦之一的黑暗騎士加里瑟斯。他們創(chuàng)立了新的種族遺族。阿爾薩斯王子回來(lái)之后，

6、與地穴領(lǐng)主阿爾克薩在克爾德加蘇的迎接下，又重新占領(lǐng)了拉達(dá)然，以變重新汲取召喚阿克蒙德時(shí)遺留下來(lái)的龐大能量，來(lái)增強(qiáng)他們不死疫軍的戰(zhàn)斗力。這引起了所有拉達(dá)然生物的憤怒。安東達(dá)尼斯之子他們?cè)谖鬟叺娜鹚固厣矫}集結(jié)了部隊(duì)進(jìn)行進(jìn)攻，而遺族也已經(jīng)與他們結(jié)盟，共同抗擊亡靈。尤迪安希望加入這個(gè)聯(lián)盟，以便擊潰亡靈，完成主人基爾加丹的任務(wù)。但他們似乎不歡迎低智力者，只有通過(guò)任務(wù)才可以加盟?，F(xiàn)在，主人把任務(wù)交給了你！【問(wèn)題描述】巴爾澤那在之前的戰(zhàn)爭(zhēng)中，將自己龐

7、大的遺族部隊(duì)n分成m個(gè)支團(tuán)，由于已經(jīng)在過(guò)去幾天前與聯(lián)盟，部落確定了總攻時(shí)間，他急需將自己的部隊(duì)盡可能集結(jié)在一個(gè)點(diǎn)上。由于需要，你可以同時(shí)調(diào)動(dòng)S支軍隊(duì)。他給了你每支軍隊(duì)的位置（xi，yi）以及每支軍隊(duì)的人數(shù)ai。由于每支軍隊(duì)的成員不同，他們的移動(dòng)速度分別為zi。你的任務(wù)是將巴爾澤那的軍隊(duì)盡可能多的集結(jié)。【輸入格式】第一行為兩個(gè)整數(shù)N表示共有N個(gè)支團(tuán)。第二行為一個(gè)整數(shù)K，S為最少集結(jié)的軍隊(duì)數(shù)目和你可以調(diào)動(dòng)的軍隊(duì)數(shù)。第三行為兩個(gè)整數(shù)C，D，為