递推与动规 - Page 15

「NOIP模拟赛」小奇挖矿
原题目名：经营与开发2015.9.13日hzwer重制了题面「题目背景」小奇要开采一些矿物，它驾驶着一台带有钻头（初始能力值w）的飞船，按既定路线依次飞过喵星系的n个星球。「问题描述」星球分为2类：资源型和维修型。 1.资源型：含矿物质量a[i]，若选择开采，则得到a[i]*p的金钱，之后钻头损耗k%，即p=p*(1-0.01k)2.维修型：维护费用b[i]，若选择维修，则支付b[i]*p的金钱，之后钻头修复c%，即p=p*(1+0.01c) （p为钻头...
02014年3月15日3,396递推与动规

「NOIP模拟赛」不等数列
不等数列(num.cpp/c/pas)「题目描述」将1到n任意排列，然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中，有多少个排列恰好有k个“<”。答案对2012取模。「输入格式」第一行2个整数n,k。「输出格式」一个整数表示答案。「样例输入」52「样例输出」66「数据范围」对于30%的数据：n<=10对于100%的数据：k<n<=1000题解f[i][j]表示前i个j个小于号的方案[crayon-67406...
02014年3月15日3,321递推与动规
数字游戏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,699递推与动规
「POJ3150」Cellular Automaton
DescriptionA cellularautomaton isacollectionofcellsonagridofspecifiedshapethatevolvesthroughanumberofdiscretetimestepsaccordingtoasetofrulesthatdescribethenewstateofacellbasedonthestatesofneighboringcells.The orderofthecellularautomaton isthenumberofcellsitcontains.Cellsoftheautomatonoforder n arenumberedfrom1to n.The orderofthecell isthenumberofdifferentvaluesitmaycontain.Usually,v...
02014年3月4日4,358递推与动规,矩阵乘法
「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,864递推与动规,深度搜索,树形动规
「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,783递推与动规
「CODEVS1403」新三国争霸
题目描述 DescriptionPP特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。在这款游戏中，加入灾害对道路的影响（也就是一旦道路W[i，j]受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路W[i，j]，至少需要K[i，j]个士兵才能守住）。PP可真是高手，不一会，...
02014年2月5日3,712递推与动规,kruskal
「JoyOI1096」数字组合
题目描述在N个数中找出其和为M的若干个数。先读入正整数N（1<N<100）和M(1<M<10000)，再读入N个正数（可以有相同的数字，每个数字均在1000以内），在这N个数中找出若干个数，使它们的和是M，把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。要求你的程序运行时间不超过1秒。输入第一行是两个数字，表示N和M。第二行起是N个数。输出就一个数字，表示和为M的...
02014年1月23日3,114递推与动规,深度搜索
「BZOJ1084」[SCOI2005] 最大子矩阵
Description这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。Input第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。Output只有一行为k个子矩阵分值之和最大为多少。SampleInput3221-323-23SampleOutput9题解[crayon-674068436c293005586954/] ...
22014年1月15日7,696递推与动规