动态规划 - Page 10

「BZOJ3611」[HEOI2014] 大工程
题面和题解见http://www.cnblogs.com/zyfzyf/p/4231356.html[crayon-674375a169e8a022456938/]
22015年1月20日6,425dfs序,虚树,树形动规,最近公共祖先

「BZOJ2286」[SDOI2011] 消耗战
Description在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总...
22015年1月20日8,312虚树,树形动规
「CF506A」Mr. Kitayuta, the Treasure Hunter
TheShusekiIslandsareanarchipelagoof30001smallislandsintheYutampoSea.Theislandsareevenlyspacedalongaline,numberedfrom0to30000fromthewesttotheeast.Theseislandsareknowntocontainmanytreasures.TherearengemsintheShusekiIslandsintotal,andthei-thgemislocatedonislandpi.Mr.Kitayutahasjustarrivedatisland0.Withhisgreatjumpingability,hewillrepeatedlyperformjumpsbetweenislandstotheeastaccordingtoth...
02015年1月19日3,362递推与动规
「火影完结纪念赛」木叶的军师
木叶的军师（nara..pas./c./cpp）时间限制：5s，空间限制：256MB题目背景：奈良鹿丸，拥有出众的应敌策略，头脑冷静、随机应变，IQ超过200。在第四次忍界大战时，父亲奈良鹿久死亡，鹿丸成为木叶乃至忍者联军的新任军师。最后成为了鸣人的左右手，与沙暴手鞠成婚……题目描述：既然是军师，鹿丸就必须要为木叶村的忍者编队。可是，他最怕麻烦了。所以它将这个任务交给了你。木叶村有T个中队，你需要将每个中队的n名忍者分为m个...
02015年1月18日4,266斜率优化
「BZOJ3696」「FJ2014集训」化合物
Description 首长NOI惨跪，于是去念文化课了。现在，他面对一道化学题。这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼，我相信你们也没有兴趣听。由于这个游戏涉及博弈论，因此化竞的同学就要求首长求一个类似SG函数的值。他们手中有一种非常神奇的化合物，它的分子由N个原子组成（不要在意一个原子可能和及其多个原子成键这个细节）。这个分子构成一个树结构，1号分子为根。 ...
02015年1月4日4,473树形动规,最近公共祖先
「CF500D」New Year Santa Network
NewYeariscominginTreeWorld!Inthisworld,asthenameimplies,therearencitiesconnectedbyn - 1roads,andforanytwodistinctcitiestherealwaysexistsapathbetweenthem.Thecitiesarenumberedbyintegersfrom1ton,andtheroadsarenumberedbyintegersfrom1ton - 1.Let'sdefined(u, v)astotallengthofroadsonthepathbetweencityuandcityv.Asanannualevent,peopleinTreeWorldrepairsexactlyoneroadperyear.Asaresult,theleng...
02015年1月4日3,716树形动规,排列组合
「POJ2404」Jogging Trails
DescriptionGordistrainingforamarathon.Behindhishouseisaparkwithalargenetworkofjoggingtrailsconnectingwaterstations.Gordwantstofindtheshortestjoggingroutethattravelsalongeverytrailatleastonce.InputInputconsistsofseveraltestcases.Thefirstlineofinputforeachcasecontainstwopositiveintegers:n<=15,thenumberofwaterstations,andm<1000,thenumberoftrails.Foreachtrail,thereisonesubsequentlineofin...
02015年1月2日4,463floyd,状压动规
「泉七培训 – 杨国烨」出纳员zgg
「题目描述」zgg去当出纳员了！zgg所在的公司的工资是按年发放的。在每年的元旦，每个员工的工资额会被修改为0元；在每年的除夕，员工按工资额领取相应的工资。zgg的上司是一位和蔼可亲的老爷爷，他经常给员工们提升工资。而zgg的工作，就是帮助所有员工统计最后的工资额。老爷爷只会用以下两种指令给员工们提升工资：1.让某个员工的工资额提升X元；2.让所有员工的工资额变成原来的X倍。然则，由于老爷爷实在是太和蔼了，以至于提...
02014年12月26日3,325树形动规
「CF498B」Name That Tune
ItturnsoutthatyouareagreatfanofrockbandAC/PE.Peterlearnedthatandstartedthefollowinggame:heplaysthefirstsongofthelistofnsongsofthegroup,andyouhavetofindoutthenameofthesong.Afteryoutellthesongname,Peterimmediatelyplaysthefollowingsonginorder,andsoon.Thei-thsongofAC/PEhasitsrecognizabilitypi.Thismeansthatifthesonghasnotyetbeenrecognizedbyyou,youlistentoitforexactlyonemoresecondandwithpr...
12014年12月25日3,581递推与动规,概率与期望
「BZOJ1485」[HNOI2009] 有趣的数列
Description 我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件： (1)它是从1到2n共2n个整数的一个排列{ai}； (2)所有的奇数项满足a1<a3<…<a2n-1，所有的偶数项满足a2<a4<…<a2n； (3)任意相邻的两项a2i-1与a2i(1≤i≤n)满足奇数项小于偶数项，即：a2i-1<a2i。现在的任务是：对于给定的n，请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大，所以只要求输...
12014年12月23日5,375递推与动规,卡特兰数
「BZOJ2281」[SDOI2011] 黑白棋
Description黑白棋（game）「问题描述」小A和小B又想到了一个新的游戏。这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。小A和小B轮流操作，现...
22014年12月22日7,059递推与动规,博弈论,排列组合
「BZOJ2595」[Wc2008] 游览计划
DescriptionInput第一行有两个整数，N和M，描述方块的数目。接下来N行，每行有M个非负整数，如果该整数为0，则该方块为一个景点；否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，行首行末也可能有多余的空格。Output由N+1行组成。第一行为一个整数，表示你所给出的方案中安排的志愿者总数目。接下来N行，每行M个字符，描述方案中相应方块的情况：z ‘_’（下划线）表示该方块没有安排志愿者...
42014年12月20日7,016状压动规