递推与动规 - Page 11

「BZOJ1638」[Usaco2007 Mar] Cow Traffic 奶牛交通
Description农场中,由于奶牛数量的迅速增长,通往奶牛宿舍的道路也出现了严重的交通拥堵问题.FJ打算找出最忙碌的道路来重点整治.这个牧区包括一个由M(1≤M≤50,000)条单行道路(有向)组成的网络,以及N(1≤N≤5,000)个交叉路口(编号为1..N),每一条道路连接两个不同的交叉路口.奶牛宿舍位于第N个路口.每一条道路都由编号较小的路口通向编号较大的路口.这样就可以避免网络中出现环.显而易见,所有道路都通向奶牛宿舍.而两个交叉...
02014年7月27日3,392递推与动规

「JoyOI1576」楼梯
描述Description在你面前有n级台阶。一个合法的走楼梯方案要满足：第一，你必须先上楼梯，到达某级后连续地下楼梯，直到返回0级。（即开始下楼梯后不能再上楼梯）第二，每次上下楼梯只能走1级或2级。第三，由于楼梯只有n级，你不能上到n级以上的位置，也不能下到0级以下的位置。问共有多少个不同的走楼梯方案。特别地，在0级站着不动也算一种方案。输入格式InputFormat一行两个正整数n和m。输出格式OutputFormat一行一个整数，...
02014年7月26日2,209递推与动规
「BZOJ2201」彩色圆环
DescriptionInput仅有一行，该行给出依次两个正整数N,M，分别表示宝石的个数和宝石在变化时可能变成的颜色种类数。Output应仅有一行，该行给出一个实数E(R)，表示圆环的“美观程度”的期望值。SampleInput81SampleOutput8.00000「数据规模和约定」100%的数据满足1≤N≤200,1≤M≤10^9。题解dp[i][j]表示前i个珠子，最后一个珠子和第一个是否相同(0,1)的期望值这样可以比较容易地得到一个n^2的转移p[i]表示i个珠子...
02014年7月25日3,001递推与动规
「BZOJ1649」[Usaco2006 Dec] Cow Roller Coaster
DescriptionThecowsarebuildingarollercoaster!Theywantyourhelptodesignasfunarollercoasteraspossible,whilekeepingtothebudget.TherollercoasterwillbebuiltonalonglinearstretchoflandoflengthL(1<=L<=1,000).TherollercoastercomprisesacollectionofsomeoftheN(1<=N<=10,000)differentinterchangablecomponents.EachcomponentihasafixedlengthWi(1<=Wi<=L).Duetovaryingterrain,eachcomponen...
02014年7月25日2,214递推与动规
「CF451D」Count Good Substrings
Wecallastring good,ifaftermergingalltheconsecutiveequalcharacters,theresultingstringispalindrome.Forexample,"aabba"isgood,becauseafterthemergingstepitwillbecome"aba".Givenastring,youhavetofindtwovalues:thenumberofgoodsubstringsofevenlength;thenumberofgoodsubstringsofoddlength.InputThefirstlineoftheinputcontainsasinglestringoflength n (1 ≤ n ≤ 105).Eachcharacterofthestringwillbeeithe...
02014年7月25日2,242递推与动规
「BZOJ1633」[Usaco2007 Feb] The Cow Lexicon 牛的词典
Description没有几个人知道,奶牛有她们自己的字典,里面的有W(1≤W≤600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她说"browndcodw",确切的意思是"browncow",多出了两个"d",这两个"d"大概是身边的噪音.奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L(2≤L≤300)的字符串.有些时候,这个字符串...
02014年7月24日2,772递推与动规
「BZOJ1643」[Usaco2007 Oct] Bessie’s Secret Pasture 贝茜的秘密草坪
Description农夫约翰已经从他的牧场中取得了数不清块数的正方形草皮，草皮的边长总是整数（有时农夫约翰割草皮的刀法不合适，甚至切出了边长为0的正方形草皮），他已经把草皮放在了一个奶牛贝茜已经知道的地方。贝茜总是希望把美味的草皮放到她的秘密庄园里，她决定从这些草皮中取出恰好4块搬到她的秘密庄园中，然后把它们分成1×1的小块，组成一个面积为N(1<=N<=10,000)个单位面积的部分。贝茜对选出这样四块草皮的方法数...
02014年7月24日2,337递推与动规
「fj夏令营」营销策略
「题目描述」W记的儿童套餐会赠送一份小玩具，赠送的小玩具共有n种。小朋友买了m份儿童套餐，求收集齐n种小玩具的概率。假设每份儿童套餐赠送的小玩具的种类是等概率随机的。「输入格式」从pattern.in中输入数据一行，两个整数n，m。「输出格式」输出到pattern.out中一个实数表示收集齐小玩具的概率，保留4位小数。「样例输入」23「样例输出」0.7500「数据规模与约定」对于10%的数据保证：n=1对于30%的数据保证：n≤2对于60%的数据...
02014年7月20日3,148递推与动规,概率与期望
「czy系列赛」czy的后宫6
czy的后宫6题目描述众所周知的是丧尸czy有很多妹子（虽然很多但是质量不容乐观QAQ），今天czy把n个妹子排成一行来检阅。但是czy的妹子的质量实在……所以czy看不下去了。检阅了第i个妹子会增加czya[i]的肾虚值，他打算在检阅过程中最多休息m次（一开始检阅算0次休息，就是说czy最多可以检阅m+1次），每次休息过后czy又会龙精虎猛的继续检阅。问怎样分配才能使得czy在检阅过程中的最大肾虚值最小。当然这么简单的问题czy早就会做...
02014年7月19日3,372递推与动规,二分法
「czy系列赛」czy的后宫4
「问题描述」czy有很多妹子，妹子虽然数量很多，但是质量不容乐观，她们的美丽值全部为负数（喜闻乐见）。czy每天都要带N个妹子到机房，她们都有一个独一无二的美丽值，美丽值为-1到-N之间的整数。他想要把这些妹子排成一个波动序列，这样相对“漂亮”（美丽值的绝对值较小）的妹子可以与她旁边的两个美丽值的绝对值较大的妹子形成鲜明的对比，整个序列相对将更加“美观”（不再那么无法直视）。一个序列是波动序列仅当序列中的每...
02014年7月19日2,856递推与动规
「BZOJ3688」「FJ2014集训」折线统计
「题目描述」二维平面上有n个点(xi,yi)，现在这些点中取若干点构成一个集合S，对它们按照x坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4部分，每部分连续上升、下降。现给定k，求满足f(S)=k的S集合个数。「输入格式」第一行两个整数n和k，以下n行每行两个数(xi,yi)表示第i个点的坐标。所有点的坐标值都在...
02014年7月13日4,172递推与动规,树状数组
「FJ互测」「BZOJ3704」昊昊的机油之GRST
题目描述(grst.c/cpp/pas)昊昊有个好机油，他就是传说中的着力点。现在昊昊获得了一份长度为n的GRST牌（mod4意义下），打算作为送给好机油的生日礼物（不是在2月的么）。但是，昊昊深知他的机油是个神犇，作为数字控的他，只会喜欢特定的序列。但是昊昊不怕，他可以使用一次菲亚特（他的机油最喜欢的大招），将一段区间内的数字全部+1，若某个数字为3，则+1后变为0。但昊昊的神力是有限的，问从初始序列a到达最终序列b，最少需...
02014年7月12日3,289递推与动规,贪心