动态规划 - Page 18

「CF453B」Little Pony and Harmony Chest
PrincessTwilightwenttoCelestiaandLuna'soldcastletoresearchthechestfromtheElementsofHarmony.Asequenceofpositiveintegers bi isharmonyifandonlyifforeverytwoelementsofthesequencetheirgreatestcommondivisorequals1.Accordingtoanancientbook,thekeyofthechestisaharmonysequence bi whichminimizesthefollowingexpression:Youaregivensequence ai,helpPrincessTwilighttofindthekey.InputThefirstlinec...
02014年8月2日3,850递推与动规,状压动规

「BZOJ1864」[ZJOI2006] 三色二叉树
DescriptionInput仅有一行，不超过500000个字符，表示一个二叉树序列。Output输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。SampleInput1122002010SampleOutput52题解随便dp一下即可f[i][0/1]表示i结点为绿/非绿色的绿色结点的最大个数转移f[x][1]=f[l[x]][0]+f[r[x]][0]+1;f[x][0]=max(f[l[x]][0]+f[r[x]][1],f[r[x]][0]+f[l[x]][1]);最小值类似[crayon-6724aec333d06666743654/] &n...
12014年8月1日4,122树形动规
「BZOJ1584」[Usaco2009 Mar] Cleaning Up 打扫卫生
Description有N头奶牛，每头那牛都有一个标号Pi，1<=Pi<=M<=N<=40000。现在FarmerJohn要把这些奶牛分成若干段，定义每段的不河蟹度为：若这段里有k个不同的数，那不河蟹度为k*k。那总的不河蟹度就是所有段的不河蟹度的总和。Input第一行：两个整数N，M第2..N+1行：N个整数代表每个奶牛的编号Output一个整数，代表最小不河蟹度SampleInput1341213223434314SampleOutput11题解不会做TT看了半天题解这...
12014年7月30日4,309递推与动规
「BZOJ1710」[Usaco2007 Open] Cheappal 廉价回文
Description为了跟踪所有的牛,农夫JOHN在农场上装了一套自动系统.他给了每一个头牛一个电子牌号当牛走过这个系统时,牛的名字将被自动读入.每一头牛的电子名字是一个长度为M(1<=M<=2,000)由N(1<=N<=26)个不同字母构成的字符串.很快,淘气的牛找到了系统的漏洞:它们可以倒着走过读码器.一头名字为"abcba"不会导致任何问题,但是名为"abcb"的牛会变成两头牛("abcb"和"bcba").农夫JOHN想改变牛的名字,使得牛的名...
02014年7月29日3,326递推与动规
「BZOJ2101」[Usaco2010 Dec] Treasure Chest 藏宝箱
DescriptionBessieandBonniehavefoundatreasurechestfullofmarvelousgoldcoins!Beingcows,though,theycan'tjustwalkintoastoreandbuystuff,soinsteadtheydecidetohavesomefunwiththecoins.TheN(1<=N<=5,000)coins,eachwithsomevalueC_i(1<=C_i<=5,000)areplacedinastraightline.BessieandBonnietaketurns,andforeachcow'sturn,shetakesexactlyonecoinoffofeithertheleftendortherightendoftheline.Thegame...
02014年7月28日3,683递推与动规
「BZOJ1672」[Usaco2005 Dec] Cleaning Shifts 清理牛棚
DescriptionFarmerJohn'scows,pamperedsincebirth,havereachednewheightsoffastidiousness.Theynowrequiretheirbarntobeimmaculate.FarmerJohn,themostobligingoffarmers,hasnochoicebuthiresomeofthecowstocleanthebarn.FarmerJohnhasN(1<=N<=10,000)cowswhoarewillingtodosomecleaning.Becausedustfallscontinuously,thecowsrequirethatthefarmbecontinuouslycleanedduringtheworkday,whichrunsfromsecondnumbe...
02014年7月28日5,057递推与动规,线段树
「BZOJ1664」[Usaco2006 Open] County Fair Events 参加节日庆祝
DescriptionFarmerJohnhasreturnedtotheCountyFairsohecanattendthespecialevents(concerts,rodeos,cookingshows,etc.).HewantstoattendasmanyoftheN(1<=N<=10,000)specialeventsashepossiblycan.He'srentedabicyclesohecanspeedfromoneeventtothenextinabsolutelynotimeatall(0timeunitstogofromoneeventtothenext!).GivenalistoftheeventsthatFJmightwishtoattend,withtheirstarttimes(1<=T<=100,000)a...
02014年7月28日3,516递推与动规
「CF452D」Washer, Dryer, Folder
Youhave k piecesoflaundry,eachofwhichyouwanttowash,dryandfold.Youareatalaundromatthathas n1 washingmachines,n2 dryingmachinesand n3 foldingmachines.Eachmachinecanprocessonlyonepieceoflaundryatatime.Youcan'tdryapieceoflaundrybeforeitiswashed,andyoucan'tfolditbeforeitisdried.Moreover,afterapieceoflaundryiswashed,itneedstobeimmediatelymovedintoadryingmachine,andafteritisdried,itneedstobei...
02014年7月28日3,184递推与动规
「BZOJ1638」[Usaco2007 Mar] Cow Traffic 奶牛交通
Description农场中,由于奶牛数量的迅速增长,通往奶牛宿舍的道路也出现了严重的交通拥堵问题.FJ打算找出最忙碌的道路来重点整治.这个牧区包括一个由M(1≤M≤50,000)条单行道路(有向)组成的网络,以及N(1≤N≤5,000)个交叉路口(编号为1..N),每一条道路连接两个不同的交叉路口.奶牛宿舍位于第N个路口.每一条道路都由编号较小的路口通向编号较大的路口.这样就可以避免网络中出现环.显而易见,所有道路都通向奶牛宿舍.而两个交叉...
02014年7月27日3,487递推与动规
「JoyOI1576」楼梯
描述Description在你面前有n级台阶。一个合法的走楼梯方案要满足：第一，你必须先上楼梯，到达某级后连续地下楼梯，直到返回0级。（即开始下楼梯后不能再上楼梯）第二，每次上下楼梯只能走1级或2级。第三，由于楼梯只有n级，你不能上到n级以上的位置，也不能下到0级以下的位置。问共有多少个不同的走楼梯方案。特别地，在0级站着不动也算一种方案。输入格式InputFormat一行两个正整数n和m。输出格式OutputFormat一行一个整数，...
02014年7月26日2,308递推与动规
「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,266递推与动规
「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,321递推与动规