递推与动规 - Page 13

「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,539递推与动规

「BZOJ1600」[Usaco2008 Oct] 建造栅栏
Description勤奋的FarmerJohn想要建造一个四面的栅栏来关住牛们。他有一块长为n（4<=n<=2500）的木板，他想把这块本板切成4块。这四块小木板可以是任何一个长度只要FarmerJohn能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意：*只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，goahead。*栅栏的面积要大于0.*输出保证答案在longint范围内。*整块木板都要用...
02014年5月22日3,502递推与动规
「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,737递推与动规
「BZOJ1296」[SCOI2009] 粉刷匠
Descriptionwindy有N条木板需要被粉刷。每条木板被分为M个格子。每个格子要被刷成红色或蓝色。windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷T次，他最多能正确粉刷多少格子？一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。Input输入文件paint.in第一行包含三个整数，NMT。接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色...
12014年5月20日5,359递推与动规,背包动规
「BZOJ1233」[Usaco2009Open] 干草堆tower
Description奶牛们讨厌黑暗。为了调整牛棚顶的电灯的亮度，Bessie必须建一座干草堆使得她能够爬上去够到灯泡。一共有N大包的干草（1<=N<=100000）(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个宽度W_i(1<=w_i<=10000)。所有的干草包的厚度和高度都为1.Bessie必须利用所有N包干草来建立起干草堆，并且按照他们进牛棚的顺序摆放。她可以相放多少包就放多少包来建立起tower的地基（当然是紧紧的放在...
12014年5月20日5,234递推与动规,单调队列
「BZOJ1668」[Usaco2006 Oct] Cow Pie Treasures 馅饼里的财富
Description最近，奶牛们热衷于把金币包在面粉里，然后把它们烤成馅饼。第i块馅饼中含有Ni(1<=Ni<=25)块金币，并且，这个数字被醒目地标记在馅饼表面。奶牛们把所有烤好的馅饼在草地上排成了一个R行(1<=R<=100)C列(1<=C<=100)的矩阵。你现在站在坐标为(1,1)的馅饼边上，当然，你可以拿到那块馅饼里的所有金币。你必须从现在的位置，走到草地的另一边，在坐标为(R,C)的馅饼旁边停止走动。每做一次移动，...
02014年5月20日3,192递推与动规
「BZOJ1898」Swamp 沼泽鳄鱼
Description潘塔纳尔沼泽地号称世界上最大的一块湿地，它地位于巴西中部马托格罗索州的南部地区。每当雨季来临，这里碧波荡漾、生机盎然，引来不少游客。为了让游玩更有情趣，人们在池塘的中央建设了几座石墩和石桥，每座石桥连接着两座石墩，且每两座石墩之间至多只有一座石桥。这个景点造好之后一直没敢对外开放，原因是池塘里有不少危险的食人鱼。豆豆先生酷爱冒险，他一听说这个消息，立马赶到了池塘，想做第一个在桥上旅游的...
02014年5月17日5,458递推与动规,矩阵乘法
「JoyOI1519」博彩游戏
背景BackgroundBob最近迷上了一个博彩游戏……描述Description这个游戏的规则是这样的：每花一块钱可以得到一个随机数R，花上N块钱就可以得到一个随机序列；有M个序列，如果某个序列是产生的随机序列的子串，那么就中奖了，否则不中。Bob会告诉你这M个序列，和身上有的钱的总数N，当然还有R的范围。请你告诉Bob中奖的概率有多少？输入格式InputFormat第一行三个用空格隔开的数N、M和R的范围R。其中1<=R<=9...
02014年5月11日3,658递推与动规,AC自动机
「NOIP模拟赛」数列
「题目描述」a[1]=a[2]=a[3]=1a[x]=a[x-3]+a[x-1] (x>3)求a数列的第n项对1000000007（10^9+7）取余的值。「输入格式」第一行一个整数T，表示询问个数。以下T行，每行一个正整数n。「输出格式」每行输出一个非负整数表示答案。「样例输入」36810「样例输出」4919「数据范围」对于30%的数据n<=100；对于60%的数据n<=2*10^7；对于100%的数据T<=100，n<=2*10^9；题解这个可以直接矩阵乘法搞掉。。[crayon-6740b415c...
32014年5月10日3,995递推与动规,矩阵乘法
「BZOJ1009」[HNOI2008] GT考试
Description阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am.A1和X1可以为0Input第一行输入N,M,K.接下来一行输入M位的数。100%数据N<=10^9,M<=20,K<=100040%数据N<=100010%数据N<=6Output阿申想知道不出现不吉利数字的号...
62014年5月9日15,348递推与动规,KMP,矩阵乘法
「BZOJ1037」[ZJOI2008] 生日聚会Party
Description今天是hidadz小朋友的生日，她邀请了许多朋友来参加她的生日party。hidadz带着朋友们来到花园中，打算坐成一排玩游戏。为了游戏不至于无聊，就座的方案应满足如下条件：对于任意连续的一段，男孩与女孩的数目之差不超过k。很快，小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现，这样的就座方案其实是很多的，所以大家很快就找到了一种，那么到底有多少种呢？热爱数学的hidadz和她的朋友们开始思考...
22014年5月6日5,469递推与动规
「BZOJ1207」[HNOI2004] 打鼹鼠
Description鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个n*n的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移...
52014年5月2日17,729递推与动规