byvoid魔獸世界邀請賽-noip2011模擬賽4

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

2、utthrough.outcondition.outsyndicate.out時間限制1s1s1s1s空間限制64MB64MB64MB64MB分值100100100100尋找尤迪安【問題描述】“阿爾薩斯王子在那刺向寒冰之冠的輝煌的那一劍，也就注定了他數(shù)年后的消亡?！薄湹衔氖钟浿刈o者的預言在諾德森一役中，幸存下來的血精靈王凱爾得知他忠效的主人—惡魔獵手尤迪安沒有死在霜之哀傷之下，而是被之前耐奧祖分流出來的力量所困??！這是一個重要的消

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

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

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

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

7、大的遺族部隊n分成m個支團，由于已經(jīng)在過去幾天前與聯(lián)盟，部落確定了總攻時間，他急需將自己的部隊盡可能集結(jié)在一個點上。由于需要，你可以同時調(diào)動S支軍隊。他給了你每支軍隊的位置（xi，yi）以及每支軍隊的人數(shù)ai。由于每支軍隊的成員不同，他們的移動速度分別為zi。你的任務是將巴爾澤那的軍隊盡可能多的集結(jié)?！据斎敫袷健康谝恍袨閮蓚€整數(shù)N表示共有N個支團。第二行為一個整數(shù)K，S為最少集結(jié)的軍隊數(shù)目和你可以調(diào)動的軍隊數(shù)。第三行為兩個整數(shù)C，D，為