2啊！神马

抄袭题！！好长的DP!!

啥也不说了。宽搜吧。稍微改改1377的代码好了。

和1377比起来有一个猥琐的地方，就是可能存在T和CT在两个连通块里面，要加判断。其他的好像没什么问题了。

图论（floyd）+DP........

这不是北京冬令营的原题吗.....

爆头不就得了，费那么大猫劲……

cS没CF好玩，玩者找我QQ:398619217

呵呵

zgx哈哈哈！

此题懒得写了，反正已经水了一次...

星火天涯因为用step 2，所以找不出第五个点对应的指数（这说明它是奇数）

这道题很BT，zgx居然说很简单？

搁浅

CS vijos貌似 还没人能虐我

( 2009-3-10 19:04:03 )

有兴趣试试？

第五个点是2493......

从468到500 step2

没有一个数是2493......

21:writeln('744282853678701455922507579277316643178128753343813693728245963960974631028119473486019635930893891134220822124816566203939432067701407744');

20:writeln('2977131414714805823690030317109266572712515013375254774912983855843898524112477893944078543723575564536883288499266264815757728270805630976');

19:writeln('11908525658859223294760121268437066290850060053501019099651935423375594096449911575776314174894302258147533153997065059263030913083222523904');

18:writeln('47634102635436893179040485073748265163400240214004076398607741693502376385799646303105256699577209032590132615988260237052123652332890095616');

17:writeln('190536410541747572716161940294993060653600960856016305594430966774009505543198585212421026798308836130360530463953040948208494609331560382464');

16:writeln('762145642166990290864647761179972242614403843424065222377723867096038022172794340849684107193235344521442121855812163792833978437326241529856');

15:writeln('3048582568667961163458591044719888970457615373696260889510895468384152088691177363398736428772941378085768487423248655171335913749304966119424');

14:writeln('12194330274671844653834364178879555881830461494785043558043581873536608354764709453594945715091765512343073949692994620685343654997219864477696');

13:writeln('48777321098687378615337456715518223527321845979140174232174327494146433419058837814379782860367062049372295798771978482741374619988879457910784');

12:writeln('195109284394749514461349826862072894109287383916560696928697309976585733676235351257519131441468248197489183195087913930965498479955517831643136');

11:writeln('780437137578998057845399307448291576437149535666242787714789239906342934704941405030076525765872992789956732780351655723861993919822071326572544');

10:writeln('3121748550315992231381597229793166305748598142664971150859156959625371738819765620120306103063491971159826931121406622895447975679288285306290176');

9:writeln('12486994201263968925526388919172665222994392570659884603436627838501486955279062480481224412253967884639307724485626491581791902717153141225160704');

8:writeln('49947976805055875702105555676690660891977570282639538413746511354005947821116249921924897649015871538557230897942505966327167610868612564900642816');

7:writeln('199791907220223502808422222706762643567910281130558153654986045416023791284464999687699590596063486154228923591770023865308670443474450259602571264');

6:writeln('799167628880894011233688890827050574271641124522232614619944181664095165137859998750798362384253944616915694367080095461234681773897801038410285056');

5:writeln('3196670515523576044934755563308202297086564498088930458479776726656380660551439995003193449537015778467662777468320381844938727095591204153641140224');

4:writeln('12786682062094304179739022253232809188346257992355721833919106906625522642205759980012773798148063113870651109873281527379754908382364816614564560896');

3:writeln('51146728248377216718956089012931236753385031969422887335676427626502090568823039920051095192592252455482604439493126109519019633529459266458258243584');

2:writeln('204586912993508866875824356051724947013540127877691549342705710506008362275292159680204380770369009821930417757972504438076078534117837065833032974336');

1:writeln('818347651974035467503297424206899788054160511510766197370822842024033449101168638720817523081476039287721671031890017752304314136471348263332131897344');

这题并不是完全抄袭；

这两题有较大不同

我的记录：http://www.vijos.cn/Record_Show.asp?id=1171554

纯属抄袭- -

还是赞下，不过我有不做一周之内不做同一种题的好习惯。。

同题传送门

http://www.vijos.cn/Problem_show.asp?id=1377

bs下= =

付上抄来的题解

---|---|---|---|---|---|-题解分割线---|---|---|---|---|---|---|

看到这道题，我们就会想到贪心。贪心有两种

A. 根本不移动，原地攻击，不成功，便成仁

反例：

00000

0111c

00CT0

11110

00000

11 5

原地不动会被包夹致死。正解请自己研究。

B. 分为移动和攻击两个阶段。移动阶段只移动，攻击阶段只原地攻击。

这个算法是对贪心A打了一个小补丁。刚才的反例固然解决了，能否保证最优呢？

反例：

00000

11111

00011

c101C

00T00

14 8

如果第一步向左或右移动一格，就白白被逼近一格。如果不移动，就会被包夹致死。正解请自己研究。

贪心就被否决了，又难以建立好的图论模型。只能采取搜索和动态规划了。

ps：本人搜索过的

一个小小小小小小优化：

大家会发现那个什么CT来着 HP会有大得有点突尤的时候。其实，当2*CT.HP大于回合数时，任务必然失败。

附自己的体会

原地死砍行不通的话，只能移动，此时你的移动若对于一个CT来讲，无论如何移动也不会让你的处境好些（多争取攻击机会），证明略（这都要写出证明的话请回家看天线宝宝(我承认我没少看)），自然二个CT也一样。

那么移动所要做的就是[尽量让两个CT走到同一格攻击你]，当然，要做到方括号里的情况也不是不论代价的，要说的这么多，其他的请大家尽情搜索吧。。。

最后ps：bs高精

好无奈

CS vijos貌似 还没人能虐我

为什么没人做这题

。。。

地板2