动态规划 - Page 23

「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,397递推与动规,KMP,矩阵乘法

「BZOJ1037」[ZJOI2008] 生日聚会Party
Description今天是hidadz小朋友的生日，她邀请了许多朋友来参加她的生日party。hidadz带着朋友们来到花园中，打算坐成一排玩游戏。为了游戏不至于无聊，就座的方案应满足如下条件：对于任意连续的一段，男孩与女孩的数目之差不超过k。很快，小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现，这样的就座方案其实是很多的，所以大家很快就找到了一种，那么到底有多少种呢？热爱数学的hidadz和她的朋友们开始思考...
22014年5月6日5,495递推与动规
「BZOJ1207」[HNOI2004] 打鼹鼠
Description鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个n*n的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移...
52014年5月2日17,776递推与动规
「BZOJ2748」[HAOI2012] 音量调节
Description一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件...
02014年4月30日5,228背包动规
「BZOJ2326」[HNOI2011] 数学作业
Description题解(F[n]) (10^k 1 1 )(F[n-1])( n )=( 0 1 1 )( n-1 )( 1 ) ( 0 0 1 )( 1 )然后分段矩阵乘法0-9,10-99…10^k-n[crayon-6770c17248362738098814/] ...
52014年4月28日7,257递推与动规,矩阵乘法
「CF417D」Cunning Gena
AboynamedGenareallywantstogettothe"RussianCodeCup"finals,oratleastgetat-shirt.Buttheofferedproblemsaretoocomplex,sohemadeanarrangementwithhis n friendsthattheywillsolvetheproblemsforhim.Theparticipantsareoffered m problemsonthecontest.Foreachfriend,Genaknowswhatproblemshecansolve.ButGena'sfriendswon'tagreetohelpGenafornothing:the i-thfriendasksGena xi rublesforhishelp insolvin...
02014年4月25日3,432状压动规
「CF417A」Elimination
Thefinalistsofthe"RussianCodeCup"competitionin2214willbetheparticipantswhowininoneoftheeliminationrounds.Theeliminationroundsaredividedintomainandadditional.Eachofthemaineliminationroundsconsistsof c problems,thewinnersoftheroundarethefirst n peopleintheratinglist.Eachoftheadditionaleliminationroundsconsistsof d problems.Thewinneroftheadditionalroundisoneperson.Besides, k winnerso...
02014年4月19日2,856背包动规
「BZOJ1677」[Usaco2005 Jan] Sumsets 求和
DescriptionFarmerJohncommandedhiscowstosearchfordifferentsetsofnumbersthatsumtoagivennumber.Thecowsuseonlynumbersthatareanintegerpowerof2.Herearethepossiblesetsofnumbersthatsumto7:1)1+1+1+1+1+1+12)1+1+1+1+1+23)1+1+1+2+24)1+1+1+45)1+2+2+26)1+2+4HelpFJcountallpossiblerepresentationsforagivenintegerN(1<=N<=1,000,000).给出一个N(1≤N≤10^6)，使用一些2的若干次幂的数相加来求之．问有多少...
02014年4月8日3,648递推与动规
「CF415D」Mashmokh and ACM
Mashmokh'sboss,Bimokh,didn'tlikeMashmokh.Sohefiredhim.MashmokhdecidedtogotouniversityandparticipateinACMinsteadoffindinganewjob.HewantstobecomeamemberofBamokh'steam.Inordertojoinhewasgivensomeprogrammingtasksandoneweektosolvethem.Mashmokhisnotaveryexperiencedprogrammer.Actuallyheisnotaprogrammeratall.Sohewasn'tabletosolvethem.That'swhyheaskedyoutohelphimwiththesetasks.Oneofthesetas...
02014年4月7日3,408递推与动规,筛法
「ch30」摆花
背景及描述艺术馆门前将摆出许多花，一共有n个位置排成一排，每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种花数量无限，求摆花的方案数。输入格式输入有1+m行，第一行有两个用空格隔开的正整数n、m，m表示花的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种花和第j种花不能排在相邻的位置，输入保证对称。（提示：同一种花可能不能排在相邻位...
02014年4月5日4,781递推与动规,矩阵乘法
「BZOJ1669」[Usaco2006 Oct] Hungry Cows饥饿的奶牛
DescriptionFarmerJohn养了N(1<=N<=5,000)头奶牛，每头牛都有一个不超过32位二进制数的正整数编号。FJ希望奶牛们在进食前，能按编号从小到大的顺序排好队，但奶牛们从不听他的话。为了让奶牛们养成这个习惯，每次开饭时，FJ从奶牛中顺序地挑出一些，这些奶牛的编号必须按挑出的顺序递增。然后FJ让被挑出的奶牛们吃饭——其他奶牛就只能饿肚子了。现在，你得到了这一次开饭前队伍中从前到后所有奶牛的编号。奶牛们...
02014年4月5日3,707递推与动规,二分法
「NOIP模拟赛」DNA序列
题目描述来自JSSI（JinkelaStateScientificInstitute）的科学家们尝试制造一个长度为N并且只包含A的DNA序列，不出意外地失败了。他们得到了一个含有A和B两种部件的序列。现在他们打算对实验结果进行篡改，来得到一个全部是A的序列。篡改的方式有两种：1更改某一位上部件的状态（A变成B，B变成A）2更改某个前缀内所有部件的状态两种操作的代价都为1。你的任务自然是求最小代价。输入第一行为N，序列长度。第二...
02014年4月5日3,421递推与动规