动态规划 - Page 26

「BZOJ1068」[SCOI2007] 压缩
Description给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程：另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。Input输入仅一行，包...
22014年3月9日6,844区间动规

「BZOJ1079」[SCOI2008] 着色方案
Description有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。Input第一行为一个正整数k，第二行包含k个整数c1,c2,...,ck。Output输出一个整数，即方案总数模1,000,000,007的结果。SampleInput3123SampleOutput10HINT 「样...
12014年3月8日5,267记忆化搜索
「NOIP模拟赛」灵魂分流药剂
问题描述皇家炼金师赫布瑞姆刚刚发明了一种用来折磨一切生物的新产品，灵魂分流药剂。灵魂分流药剂的妙处在于能够给服用者带来巨大的痛苦，但是却不会让服用者死去，而且可以阻止服用者的自杀。用它来对付敢于反对希尔瓦娜斯女王的狂徒们，简直是太精妙了。最近，侦察兵抓获了一个来自暴风城的人类探子，希尔瓦娜斯女王命令你用最痛苦的手段来折磨他。你拥有N瓶药剂，按照成分配比的不同装在M个箱子中。每瓶药剂的有以下参...
12014年3月7日2,736背包动规
数字游戏II
http://218.5.5.242:9018/JudgeOnline/problem.php?id=1440题目描述　　小W发明了一个游戏，他在黑板上写出了一行数字a1，a2，…an，然后给你m个回合的机会，每回合你可以从中选择一个数擦去它，接着剩下来的每个数字ai都要递减一个值bi如此重复m个回合，所有你擦去的数字之和就是你所得到的分数。小W和他的好朋友小Y玩了这个游戏，可是他发现，对于每个给出的an和bn序列，小Y的得分总是比他高。小W很不服气，想让你帮他算算...
02014年3月4日3,745递推与动规
「JoyOI1468」清理垃圾
背景Background聚会结束，留下许多垃圾。Candy：“好多垃圾啊，飘飘乎居士，我们一起处理垃圾吧！”描述DescriptionCandy家里总共有n个垃圾等待处理，每个垃圾对于Candy和飘飘乎居士处理的时间都是不同的，而且每个垃圾只需要一个人处理。当然，Candy和飘飘乎居士可以同时处理不同的垃圾。记两人中耗费最长时间为最后总时间。Candy希望能够尽快的处理完所有的垃圾，因此，他想要知道处理完这些垃圾最少需要耗费多少时间？输...
02014年3月4日2,701递推与动规
「POJ3150」Cellular Automaton
DescriptionA cellularautomaton isacollectionofcellsonagridofspecifiedshapethatevolvesthroughanumberofdiscretetimestepsaccordingtoasetofrulesthatdescribethenewstateofacellbasedonthestatesofneighboringcells.The orderofthecellularautomaton isthenumberofcellsitcontains.Cellsoftheautomatonoforder n arenumberedfrom1to n.The orderofthecell isthenumberofdifferentvaluesitmaycontain.Usually,v...
02014年3月4日4,358递推与动规,矩阵乘法
「JoyOI1466」最美妙的矩阵
背景BackgroundCandy的生日即将到来，飘飘乎居士希望找到一个最美妙的矩阵送个Candy作为礼物描述Description飘飘乎居士从Pink处得知最美妙的矩阵满足三个条件：首先，它的长和宽都必须和矩阵的边界平行（也就是不可以出现斜的矩阵）；第二：子矩阵横竖都要满足单调递增（可以相等，也就是对于每一个最优子矩阵的元素都要满足a[i][j]>=a[i-1][j] and a[i][j]>=a[i][j-1]，其中a[i][j]表示矩阵第i行第j列的数字）；第三...
02014年3月3日3,743区间动规
「wiki1281」Xn数列
题目描述 Description给你6个数，m,a,c,x0,n,gXn+1 =(aXn +c)modm，求Xnm,a,c,x0,n,g<=10^18输入描述 InputDescription一行六个数 m,a,c,x0,n,g输出描述 OutputDescription输出一个数 Xn modg样例输入 SampleInput1187153样例输出 SampleOutput2数据范围及提示 DataSize&Hintint64按位相乘可以不要用高精度。题解由题目中Xn+1 =(a*Xn +c)%m可得以下矩阵：┏a,0┓[Xn,c]*┃ ┃=[Xn+...
02014年3月3日3,381递推与动规,矩阵乘法
「POJ3070」Fibonacci
DescriptionIntheFibonacciintegersequence, F0 =0, F1 =1,and Fn = Fn −1 + Fn −2 for n ≥2.Forexample,thefirsttentermsoftheFibonaccisequenceare:0,1,1,2,3,5,8,13,21,34,…AnalternativeformulafortheFibonaccisequenceis.Givenaninteger n,yourgoalistocomputethelast4digitsof Fn.InputTheinputtestfilewillcontainmultipletestcases.Eachtestcaseconsistsofasinglelinecontainingn(wh...
02014年3月3日5,130递推与动规,矩阵乘法
「BZOJ1040」[ZJOI2008] 骑士
DescriptionZ国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相...
02014年2月26日8,865递推与动规,深度搜索,树形动规
「BZOJ1076」[SCOI2008] 奖励关
Description你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出k次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。宝物一共有n种，系统每次抛出这n种宝物的概率都相同且相互独立。也就是说，即使前k-1次系统都抛出宝物1（这种情况是有可能出现的，尽管概率非常小），第k次抛出各个宝物的概率依然均为1/n。获取第i种宝物将得...
12014年2月7日8,049状压动规,概率与期望
「JoyOI1088」treat
题目描述给出长度为N的数列{A_i}，每次可以从最左边或者最右边取走一个数，第i次取数得到的价值是i * A_j。求价值之和最大的取数方案。输入第一行，一个整数，表示数列长度N。接下来N行，每行一个整数，表示数列A_i。输出一个整数，表示最大的价值之和。样例输入513152样例输出43提示N <= 2000 , A_i <= 1000题解dp或者记忆化搜索。。f[i][j]表示左边取i个右边j个最大价值，方程比较好想。。[crayon...
02014年2月5日2,785递推与动规