BYVoid魔獸世界邀請賽-NOIP2011模擬賽4.doc

BYVoid魔獸世界邀請賽-NOIP2011模擬賽 v（搜索與DP）之血精靈AND娜迦專場測試時間：3小時【題目一覽】題號第一題第二題第三題第四題題目名稱尋找尤迪安橫渡法斯琪條件巴爾澤那被證實的預言提交文件find.pas/c/cppthrough.pas/c/cppcondition.pas/c/cppsyndicate.pas/cpp輸入文件hrough.incondition.insyndicate.in輸出文件find.outthrough.outcondition.outsyndicate.out時間限制1s1s1s1s空間限制64MB64MB64MB64MB分值100100100100尋找尤迪安【問題描述】 “阿爾薩斯王子在那刺向寒冰之冠的輝煌的那一劍，也就注定了他數(shù)年后的消亡?！丙湹衔氖钟浿刈o者的預言在諾德森一役中，幸存下來的血精靈王凱爾得知他忠效的主人惡魔獵手尤迪安沒有死在霜之哀傷之下，而是被之前耐奧祖分流出來的力量所困住！這是一個重要的消息。但是，耐奧祖的力量形成了一個龐大的磁場矩陣，而在這個磁場內(nèi)行走需要魔法，這對魔法充滿渴望的血精靈來說是一個噩夢，但是必須找到主人！血精靈們發(fā)現(xiàn)，這個矩陣內(nèi)有許多能量溢出點，他們可以用這些溢出的能量來補充魔法。能量溢出點的能量用完后，則變?yōu)槠降?。你就是凱爾，你需要在磁場矩陣中走最少的步數(shù)來救你的主人，當然，聰明的你會使用最少的魔法的?！据斎敫袷健?第一行為一個整數(shù)N，表示一個N*N的矩陣。（N50） 接下來N+1行為矩陣的描述，其中0為空地，1為磁場，不可通行，3為能量溢出點。 接下來一行，為兩個整數(shù)A，B，表示凱爾的魔法初始值和每個能量溢出點能補充的魔法。 提示（凱爾初始位置默認為（1,1），尤迪安的默認位置為（N，N）【輸出格式】 輸出文件為兩行，第一行為最少步數(shù)，第二行為最少使用魔法值。（由于劇情需要，數(shù)據(jù)不提供無解）。 【輸入輸出樣例】輸入：50 0 0 0 30 1 0 0 01 1 0 3 00 1 1 1 00 0 0 0 05 4輸出：84（能量溢出點提供的魔法所消耗不算）橫渡法斯琪【問題描述】 你成功的就出了主人尤迪安，他召集了部下-娜迦族。但他發(fā)現(xiàn)，海妖們并沒有過來。他通過橫渡的瓦格里爾-娜迦暴徒們口中的知海妖們和她們的領(lǐng)袖法斯琪女士正在與洛倫丹邊境的亡靈們作戰(zhàn)。尤迪安召集了一些船只運送他的部隊。但是，光靠現(xiàn)有的部隊去擊潰亡靈們是遠遠不夠的。幸運的是，在海洋上，有許多正在橫渡的娜迦族們。如果靠近他們，他們會自愿加入。但是航行需要時間，你必須在最短的時間內(nèi)到達并援助法斯琪女士?！据斎敫袷健康谝恍袨閮蓚€整數(shù)N，M，表示一個N*M的矩陣。（M=N75）接下來N+1行為矩陣的描述，其中每個格子都有一個數(shù)字來描述航行所要的時間。如果該格子有娜迦族，則用字母表示。A代表有1名娜迦族人，B表示有兩名，以此類推，而航行時間默認為1。接下來的一行為兩個整數(shù)A,B，表示初始兵力A與所需兵力B?！据敵龈袷健?輸出文件為一行，表示最短天數(shù)。（由于劇情需要，數(shù)據(jù)不提供無解）?！据斎胼敵鰳永枯斎耄? 50 2 5 6 92 A B 1 10C E 1 6 57 7 1 1 5A A A A 012 19輸出：8條件巴爾澤那【問題背景】 你成功的消滅了洛倫丹邊境的亡靈軍隊。但是細心的法斯琪女士發(fā)現(xiàn)，他們的力量似乎不來自于巫妖王-阿爾薩斯。而且缺失了重要的成員-亡靈巫師。那是巫妖-克爾德加蘇的信徒們。似乎在洛倫丹，亡靈的統(tǒng)治發(fā)生了巨變。翌日，法斯琪的想法得到了證實。洛倫丹亡靈新的統(tǒng)治者之一，恐懼魔王-巴爾澤那找上了尤迪安。原來，在阿爾薩斯王子的諾德森之戰(zhàn)中，巴爾澤那與追風者-西瓦娜動了政變，攻占了洛倫丹人類人類聯(lián)盟的首都并殺死了原先的統(tǒng)治者-恐懼魔王-德拉瑞克特與聯(lián)盟首腦之一的黑暗騎士-加里瑟斯。他們創(chuàng)立了新的種族-遺族。阿爾薩斯王子回來之后，與地穴領(lǐng)主-阿爾克薩在克爾德加蘇的迎接下，又重新占領(lǐng)了拉達然，以變重新汲取召喚阿克蒙德時遺留下來的龐大能量，來增強他們不死疫軍的戰(zhàn)斗力。這引起了所有拉達然生物的憤怒。安東達尼斯之子他們在西邊的瑞斯特山脈集結(jié)了部隊進行進攻，而遺族也已經(jīng)與他們結(jié)盟，共同抗擊亡靈。尤迪安希望加入這個聯(lián)盟，以便擊潰亡靈，完成主人基爾加丹的任務。但他們似乎不歡迎低智力者，只有通過任務才可以加盟?，F(xiàn)在，主人把任務交給了你！【問題描述】 巴爾澤那在之前的戰(zhàn)爭中，將自己龐大的遺族部隊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，為集結(jié)地點。 第四行為一個整數(shù)，Q表示共有的Q個時間。 接下來的M行，為四個整數(shù)（xi，yi，ai，zi）其中xi與yi描述的是第I支軍隊的位