动态规划 - Page 21

「NOIP模拟赛」某种数列问题
题目描述众所周知，czy97有无数的妹子(阿掉！>_<)，而且他还有很多恶趣味的问题，继上次纠结于一排妹子的排法以后，今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的妹子站成一排，然后对于每个妹子有一个美丽度，当然美丽度越大越好，chenzeyu97妹子很多，但是质量上不容乐观，经常出现很多美丽度为负数的妹子(喜闻乐见)，czy97希望从一排妹子里找出3队连续的妹子，使她们的美丽度和最大。注意，一...
02014年6月1日3,560递推与动规

「BZOJ1592」[Usaco2008 Feb] Making the Grade 路面修整
DescriptionFJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能同时出现在修好的路中。整条路被分成了N段，N个整数A_1,...,A_N(1<=N<=2,000)依次描述了每一段路的高度(0<=A_i<=1,000,000,000)。FJ希望找到一个恰好含N个元素的不上升或不下降序列B_1,...,B_N，作为修过的路中每个路段的高度。由于将每一段路...
72014年5月29日4,122递推与动规
「BZOJ1537」[POI2005] Aut – The Bus
DescriptionByteCity的街道形成了一个标准的棋盘网络–他们要么是北南走向要么就是西东走向.北南走向的路口从1到n编号,西东走向的路从1到m编号.每个路口用两个数(i,j)表示(1<=i<=n,1<=j<=m).ByteCity里有一条公交线,在某一些路口设置了公交站点.公交车从(1,1)发车,在(n,m)结束.公交车只能往北或往东走.现在有一些乘客在某些站点等车.公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.I...
02014年5月28日3,721递推与动规,树状数组
「BZOJ1004」[HNOI2008] Cards
Description小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案.最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可...
22014年5月26日9,340背包动规,置换,乘法逆元
「JoyOI1617 / 2062」偷葡萄(grape)
描述Descriptionfox来到了一排葡萄架下,葡萄架上有很多葡萄(n串),它想将一部分葡萄偷走.每串葡萄都有一个价值,当然,由于有酸有甜,葡萄的价值可能为正,也可能为负.当然,为了让农夫看不出来,fox规定,每k串葡萄中,它最多选b串,但是由于fox是比较贪心的,每连续k串葡萄中,它会最少选a串例如n=5 k=3 a=1 b=2时,在第1--第3串葡萄中,fox只能选1或2串,在第2--第4串葡萄中,fox也只能选1或2串.图1的选法是不合法的,因为2--4中选出了3串葡萄...
02014年5月25日3,025状压动规
「BZOJ2442」[Usaco2011 Open] 修剪草坪
Description在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N(1<=N<=100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，奶牛i的效率为E_i(0<=E_i<=1,000,000,000)。靠近的奶牛们很熟悉，因此，如果FJ安排超过K只连续的奶牛，...
92014年5月24日6,673递推与动规,单调队列
「BZOJ1642」[Usaco2007 Nov] Milking Time 挤奶时间
Description贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的N(1≤N≤1,000,000)个小时，标记为0..N-1。FarmerJohn计划好了M(1≤M≤1,000)个可以挤奶的时间段。每个时间段有一个开始时间(0≤开始时间≤N),和一个结束时间(开始时间<结束时间≤N),和一个产量(1≤产量≤1,000,000)表示可以从贝茜挤奶的数量。FarmerJohn从分别从开始时间挤奶，到结束时间为止。每次挤奶...
02014年5月23日3,000递推与动规
「BZOJ1679」[Usaco2005 Jan] Moo Volume 牛的呼声
DescriptionFarmerJohnhasreceivedanoisecomplaintfromhisneighbor,FarmerBob,statingthathiscowsaremakingtoomuchnoise.FJ'sNcows(1<=N<=10,000)allgrazeatvariouslocationsonalongone-dimensionalpasture.Thecowsareverychattyanimals.Everypairofcowssimultaneouslycarriesonaconversation(soeverycowissimultaneouslyMOOingatalloftheN-1othercows).WhencowiMOOsatcowj,thevolumeofthisMOOmustbee...
02014年5月23日3,477递推与动规
「BZOJ1617」River Crossing渡河问题
DescriptionFarmerJohn以及他的N(1<=N<=2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。由于奶牛不会划船，在整个渡河过程中，FJ必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加1，FJ把木筏划到对岸就得花更多的时间。当FJ一个人坐在木筏上，他把木筏划到对岸需要M(1<=M<=1000)分钟。当木筏搭载的奶牛数目从i-1增加到i时，FJ得多花M_i(1<=M_i<=1000)分钟才能把木筏...
02014年5月22日3,585递推与动规
「BZOJ1600」[Usaco2008 Oct] 建造栅栏
Description勤奋的FarmerJohn想要建造一个四面的栅栏来关住牛们。他有一块长为n（4<=n<=2500）的木板，他想把这块本板切成4块。这四块小木板可以是任何一个长度只要FarmerJohn能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意：*只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，goahead。*栅栏的面积要大于0.*输出保证答案在longint范围内。*整块木板都要用...
02014年5月22日3,521递推与动规
「BZOJ1260」[CQOI2007] 涂色paint
Description假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。用尽量少的涂色次数达到目标。Input输入仅一行，包含一个长度为n的字符串，即涂色目...
02014年5月22日5,840区间动规
「CF431C」k – Tree
QuiterecentlyacreativestudentLeshahadalectureontrees.AfterthelectureLeshawasinspiredandcameupwiththetreeofhisownwhichhecalleda k-tree.A k-treeisaninfiniterootedtreewhere:eachvertexhasexactly k children;eachedgehassomeweight;ifwelookattheedgesthatgoesfromsomevertextoitschildren(exactly k edges),thentheirweightswillequal 1, 2, 3, ..., k.Thepicturebelowshowsapartofa3-tree. ...
02014年5月22日3,757递推与动规