动态规划 - Page 14

「NOIP模拟赛」LazyChild黑OJ
LazyChild开了一家“善良OJ”。但大多数人都不知道，这其实是家黑OJ。亲爱的同学，请不要惊讶，古时候有黑店，现代为什么不能有黑OJ呢？每AC一道题，网站便会自动在电脑上安装一种木马。LazyChild通过窃取信息获取收益（如网游帐号、OI资料、YuanY和TT的照片等等）。作为一名资深黑客，老Z某日突然发现，“善良OJ”上的木马，自己电脑上都没有。这可十分让他过意不去。老Z决定通过多A题，来丰富自己电脑的病...
02014年11月2日3,603树形动规

「NOIP模拟赛」迎接仪式
「问题描述」LHX教主要来X市指导OI学习工作了。为了迎接教主，在一条道路旁，一群Orz教主er穿着文化衫站在道路两旁迎接教主，每件文化衫上都印着大字。一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字，但是领队突然发现，另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐。为了简单描述这个不和谐的队列，我们用“j”替代“教”，“z”替代“主”。而一个“j”与“z”组成的序列则可以描述当前的队列。为了让教主...
02014年11月2日2,785递推与动规
「NOIP模拟赛」日历游戏
「问题描述」moreD和moreD的宠物CD正在玩一个日历游戏，开始时，他们从1900年1月1日到2012年12月22日（你懂的……）选一个日期开始，依次按照如下规则之一向后跳日期：1.跳到日历上的下一天。2.跳到日历上的下个月的同一天（如果不存在，则不能这么做）。要是谁正好到达2012年12月22日那么他就赢了，如果到达这天之后的日期那他就输了——原因你也懂的。每次都是moreD先走的。现在，给你一个日期，请问moreD一定能赢吗？「输...
02014年11月2日5,031博弈论,记忆化搜索
「NOIP模拟赛」小象涂色
题目描述：小象喜欢为箱子涂色。小象现在有c种颜色，编号为0~c-1；还有n个箱子，编号为1~n，最开始每个箱子的颜色为1。小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择[L，R]这个区间里的一些箱子（不选看做选0个），为之涂上随机一种颜色。若一个颜色为a的箱子被涂上b色，那么这个箱子的颜色会变成（a*b）modc。请问在k次涂色后，所有箱子颜色的编号和期望为多少？输入描述：第一行为T，表示有T组测...
02014年10月31日3,095递推与动规
「NOIP模拟赛」Kth
「题目描述」给定一个N(2<=N<=150000)个节点N－1边的树，每条边有一个长度L（1<=L<=1000000）。现在定义：“路径(u,v)长度”表示顶点u到v之间的最短路径“u的第k远路径”表示从顶点u出发的第k长路径。请编写一个程序，计算这棵树中每个顶点的的第k远路径的长度。「输入格式」输入第一行包含一个整数T（T<=50），表示测试数据的组数。在每一组测试数据中，第一行为两个整数N和K(1<=K<=20且K<=N...
02014年10月30日3,789树形动规
「hdu2196」Computer
ProblemDescriptionAschoolboughtthefirstcomputersometimeago(sothiscomputer'sidis1).DuringtherecentyearstheschoolboughtN-1newcomputers.Eachnewcomputerwasconnectedtooneofsettledearlier.ManagersofschoolareanxiousaboutslowfunctioningofthenetandwanttoknowthemaximumdistanceSiforwhichi-thcomputerneedstosendsignal(i.e.lengthofcabletothemostdistantcomputer).Youneedtoprovidethisinformation.Hint:the...
02014年10月30日3,897树形动规
「NOIP模拟赛」Incr
「题目描述」数列A1,A2,...,AN，修改最少的数字，使得数列严格单调递增。「输入格式」第1行，1个整数N第2行，N个整数A1,A2,...,AN「输出格式」1个整数，表示最少修改的数字「样例输入」3132「样例输出」1「数据范围」对于50%的数据，N≤10^3对于100%的数据，1≤N≤10^5,1≤Ai≤10^9题解暴力可以用f[i][j]表示前i个最后一个改为j的方案[crayon-672474cc337d8176692723/]ai减去下标求最长上升子序列ans。。。答案是n-an...
02014年10月30日2,826递推与动规
「NOIP模拟赛」宠物之战
「问题描述」众所周知，moreD的宠物已经被moreD奴役得体无完肤。这只宠物实在忍无可忍，把自己每天走魔法树的经历告诉了自己的宠物。同时他还说明了自己爬树是多么地慢，以至于moreD每天都残酷地训练他爬树。幸运的是moreD的宠物的宠物不是moreD的宠物，moreD的宠物深知”宠物是用来宠的而不是用来奴役的”这一点，所以moreD的宠物对待自己的宠物很有爱。所以moreD的宠物与其宠物商量着要推翻moreD的暴政，方法是把moreD...
02014年10月29日2,637树形动规
「BZOJ2708」[Violet 1] 木偶
DescriptionInputOutputSampleInput121542893123256603595957351555951232448770813445055585961234566123345812334254922235261393814017SampleOutput00010001002221HINTSourcef[i]=f[j]+cal(j+1,i)cal(x,y)计算x-y互相匹配最多可扔掉几个枚举可以扔掉的数量k，判断剩下的能否相互匹配，不能返回k-1以及被扔掉的能否相互匹配，能匹配返回k-1[crayon-672474cc33f1a083409129/] ...
02014年10月26日3,163递推与动规,贪心
「NOIP模拟赛」班服
题目描述：要开运动会了，神犇学校的n个班级要选班服，班服共有100种样式，编号1~100。现在每个班都挑出了一些样式待选，每个班最多有100个待选的样式。要求每个班最终选定一种样式作为班服，且该班的样式不能与其他班级的相同，求所有可能方案的总数，由于方案总数可能很大，所以要求输出mod1000000007后的答案。输入描述：共有T组数据。对于每组数据，第一行为一个整数n，表示有n个班级。2~n+1行，每行有最多100个数字，表示第i...
02014年10月25日3,687状压动规
「NOIP模拟赛」土豪聪要请客
众所周知，聪哥(ndsf)是个土豪，不过你们不知道的是他的MZ和他的RMB一样滴多……某天土豪聪又赚了10^10000e的RMB，他比较开心，于是准备请客。他在自己在XX星上的别墅里面大摆酒席，想要邀请尽可能多的MZ来参加他的宴会。他将会同MZ一起坐在一个巨大的长方形桌子上。这个桌子能坐下的人数等于他的边长。聪哥要求他的桌子能够放进他的别墅，并且桌子的边必须与别墅的边界平行。给定别墅的平面图，请你求出聪哥最多可以...
32014年10月23日4,076递推与动规
「JoyOI1097」MM不哭
描述Description在一个数轴上,有n个MM(绝非恐龙!)在哭泣(5555~一直哭).tcboy也在这个数轴上,并恰好看到了这一幕,由于每个MM哭都会让tcboy损失一定的rp,于是tcboy有必要去安慰她们.(真命苦啊 T.T)开始时，tcboy站在k号MM的旁边.现在知道第i个MM哭泣每秒钟会使tcboy降低 w[i]的rp (单位rp/s).而tcboy的行走速度很慢只有1m/s .tcboy安慰MM的方式很特别(怎么安慰随便大家YY了..#@$%^%$#@),不需要花费时间.请计算tcb...
02014年10月22日2,511递推与动规