动态规划 - Page 15

「BZOJ2091」The Minima Game
Description给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下，最终A的得分减去B的得分为多少。Input第一行一个正整数N(N<=1,000,000)，第二行N个正整数（不超过10^9）。Output一个正整数，表示最终A与B的分差。SampleInput3131SampleOutput2HINT第一次A...
02014年10月20日2,283递推与动规

「CF480C」Riding in a Lift
Imaginethatyouareinabuildingthathasexactlynfloors.Youcanmovebetweenthefloorsinalift.Let'snumberthefloorsfrombottomtotopwithintegersfrom1ton.Nowyou'reonthefloornumbera.Youareverybored,soyouwanttotakethelift.Floornumberbhasasecretlab,theentryisforbidden.However,youalreadyareinthemoodanddecidetomakekconsecutivetripsinthelift.Letussupposethatatthemomentyouareonthefloornumberx(initially,youwere...
02014年10月20日2,473递推与动规
「BZOJ1097」[POI2007] 旅游景点atr
DescriptionFGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅行的距离尽量短，这样他就有足...
02014年10月19日5,402dijkstra,状压动规
「NOIP模拟赛」警察叔叔就是这个人！
题目背景十个地方十人十色全部都是猥琐大叔这里也是那里也是行踪可疑现如今hentai横行，警察叔叔们不得不采取特♂殊手段惩戒这些家伙题目描述魅力之都是一个有N个路口，M条双向道路连接的城市。警察叔叔绘制了一张特殊的地图，在地图上只保留了N-1条道路，我们称这些道路为「特殊道路」，要保证任意两个路口间有且仅有一条路径，且满足所有保留的道路长度之和最小。现在要在其中一个连接有多条「特殊道路」的路口设立「根据地」...
02014年10月18日3,548树形动规
「CF100506」Pachinko
PachinkoisaJapanesegameplayedforamusementandprizes,andissimilartopinball.Thegameisverysimple:youshootsmallmetalballsintothemachineandtheyfalldown,bouncingofftheobstaclesuntiltheyfallintoagate.Thegateintowhichyourballfallsdeterminesthewinnings.Sinceyoucanmoreorlessdeterminethecolumnintowhichtheballisdropped(bysettingitsinitialspeedanddirection),youcaninfluenceyourwinchances.Youaretocalculatey...
02014年10月18日2,987递推与动规
「CF478D」Red – Green Towers
Therearerredandggreenblocksforconstructionofthered-greentower.Red-greentowercanbebuiltfollowingnextrules:Red-greentowerisconsistingofsomenumberoflevels;Letthered-greentowerconsistofnlevels,thenthefirstlevelofthistowershouldconsistofnblocks,secondlevel—ofn - 1blocks,thethirdone—ofn - 2blocks,andsoon—thelastlevelofsuchtowershouldconsistoftheoneblock.Inotherwords,eachsuccessivelevelshould...
02014年10月17日4,019递推与动规
「CF477C」Dreamoon and Strings
Dreamoonhasastringsandapatternstringp.Hefirstremovesexactlyxcharactersfromsobtainingstrings'asaresult.Thenhecalculatesthatisdefinedasthemaximalnumberofnon-overlappingsubstringsequaltopthatcanbefoundins'.Hewantstomakethisnumberasbigaspossible.Moreformally,let'sdefineasmaximumvalueofoveralls'thatcanbeobtainedbyremovingexactlyxcharactersfroms.Dreamoonwantstoknowforallxfrom0to|s|where|s|denotest...
02014年10月13日4,854递推与动规
「BZOJ1131」[POI2008] Sta
Description给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大Input给出一个数字N,代表有N个点.N<=1000000下面N-1条边.Output输出你所找到的点,如果具有多个解,请输出编号最小的那个.SampleInput814564567682434SampleOutput7题解发现从根从某个位置移到它的一个子树得出ans只要O1的时间那么树形dp即可[crayon-6743c7e50807e658204263/] ...
02014年10月11日3,503树形动规
「BZOJ1023」[SHOI2008] cactus仙人掌图
Description如果某个无向连通图的任意一条边至多只出现在一条简单回路（simplecycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也...
22014年10月10日10,459递推与动规,单调队列,仙人掌
「BZOJ1072」[SCOI2007] 排列perm
Description给一个数字串s和正整数d,统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。Input输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0,1,2,3,4,5,6,7,8,9.Output每个数据仅一行，表示能被d整除的排列的个数。SampleInput7000100111234567890112343421234712345171234567829SampleOutput13...
02014年10月10日5,197状压动规
「BZOJ1833」[ZJOI2010] count 数字计数
Description给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。Input输入文件中仅包含一行两个整数a、b，含义如上所述。Output输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。SampleInput199SampleOutput9202020202020202020HINT30%的数据中，a<=b<=10^6；100%的数据中，a<=b<=10^12。题解裸的数位dp大概只有我这种逗比不会做递推出f[i][j][k]表示长度为i开头...
02014年10月9日8,372数位动规
「BZOJ1093」[ZJOI2007] 最大半连通子图
DescriptionInput第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。接下来M行，每行两个正整数a,b，表示一条有向边(a,b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。Output应包含两行，第一行包含一个整数K。第二行包含整数CModX.SampleInput6620070603122113245664SampleOutput33HINT对于100%的数据，N≤100000,M≤1000000；对于100%的数据，X≤...
22014年10月8日7,486递推与动规,拓扑排序,图的连通