BYVoid魔獸世界邀請(qǐng)賽-NOIP2011模擬賽4.doc

BYVoid魔獸世界邀請(qǐng)賽-NOIP2011模擬賽 v（搜索與DP）之血精靈AND娜迦專場(chǎng)測(cè)試時(shí)間：3小時(shí)【題目一覽】題號(hào)第一題第二題第三題第四題題目名稱尋找尤迪安橫渡法斯琪條件巴爾澤那被證實(shí)的預(yù)言提交文件find.pas/c/cppthrough.pas/c/cppcondition.pas/c/cppsyndicate.pas/cpp輸入文件hrough.incondition.insyndicate.in輸出文件find.outthrough.outcondition.outsyndicate.out時(shí)間限制1s1s1s1s空間限制64MB64MB64MB64MB分值100100100100尋找尤迪安【問(wèn)題描述】 “阿爾薩斯王子在那刺向寒冰之冠的輝煌的那一劍，也就注定了他數(shù)年后的消亡?！丙湹衔氖钟浿刈o(hù)者的預(yù)言在諾德森一役中，幸存下來(lái)的血精靈王凱爾得知他忠效的主人惡魔獵手尤迪安沒(méi)有死在霜之哀傷之下，而是被之前耐奧祖分流出來(lái)的力量所困??！這是一個(gè)重要的消息。但是，耐奧祖的力量形成了一個(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è)N*N的矩陣。（N50） 接下來(lái)N+1行為矩陣的描述，其中0為空地，1為磁場(chǎng)，不可通行，3為能量溢出點(diǎn)。 接下來(lái)一行，為兩個(gè)整數(shù)A，B，表示凱爾的魔法初始值和每個(gè)能量溢出點(diǎn)能補(bǔ)充的魔法。 提示（凱爾初始位置默認(rèn)為（1,1），尤迪安的默認(rèn)位置為（N，N）【輸出格式】 輸出文件為兩行，第一行為最少步數(shù)，第二行為最少使用魔法值。（由于劇情需要，數(shù)據(jù)不提供無(wú)解）。 【輸入輸出樣例】輸入：50 0 0 0 30 1 0 0 01 1 0 3 00 1 1 1 00 0 0 0 05 4輸出：84（能量溢出點(diǎn)提供的魔法所消耗不算）橫渡法斯琪【問(wèn)題描述】 你成功的就出了主人尤迪安，他召集了部下-娜迦族。但他發(fā)現(xiàn)，海妖們并沒(méi)有過(guò)來(lái)。他通過(guò)橫渡的瓦格里爾-娜迦暴徒們口中的知海妖們和她們的領(lǐng)袖法斯琪女士正在與洛倫丹邊境的亡靈們作戰(zhàn)。尤迪安召集了一些船只運(yùn)送他的部隊(duì)。但是，光靠現(xiàn)有的部隊(duì)去擊潰亡靈們是遠(yuǎn)遠(yuǎn)不夠的。幸運(yùn)的是，在海洋上，有許多正在橫渡的娜迦族們。如果靠近他們，他們會(huì)自愿加入。但是航行需要時(shí)間，你必須在最短的時(shí)間內(nèi)到達(dá)并援助法斯琪女士?！据斎敫袷健康谝恍袨閮蓚€(gè)整數(shù)N，M，表示一個(gè)N*M的矩陣。（M=N75）接下來(lái)N+1行為矩陣的描述，其中每個(gè)格子都有一個(gè)數(shù)字來(lái)描述航行所要的時(shí)間。如果該格子有娜迦族，則用字母表示。A代表有1名娜迦族人，B表示有兩名，以此類推，而航行時(shí)間默認(rèn)為1。接下來(lái)的一行為兩個(gè)整數(shù)A,B，表示初始兵力A與所需兵力B。【輸出格式】 輸出文件為一行，表示最短天數(shù)。（由于劇情需要，數(shù)據(jù)不提供無(wú)解）?！据斎胼敵鰳永枯斎耄? 50 2 5 6 92 A B 1 10C E 1 6 57 7 1 1 5A A A A 012 19輸出：8條件巴爾澤那【問(wèn)題背景】 你成功的消滅了洛倫丹邊境的亡靈軍隊(duì)。但是細(xì)心的法斯琪女士發(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)之后，與地穴領(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)中，將自己龐大的遺族部隊(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，為集結(jié)地點(diǎn)。 第四行為一個(gè)整數(shù)，Q表示共有的Q個(gè)時(shí)間。 接下來(lái)的M行，為四個(gè)整數(shù)（xi，yi，ai，zi）其中xi與yi描述的是第I支軍隊(duì)的位