动态规划 - Page 24

「BZOJ1616」[Usaco2008 Mar] Cow Travelling游荡的奶牛
Description奶牛们在被划分成N行M列(2<=N<=100;2<=M<=100)的草地上游走，试图找到整块草地中最美味的牧草。FarmerJohn在某个时刻看见贝茜在位置(R1,C1)，恰好T(0<T<=15)秒后，FJ又在位置(R2,C2)与贝茜撞了正着。FJ并不知道在这T秒内贝茜是否曾经到过(R2,C2)，他能确定的只是，现在贝茜在那里。设S为奶牛在T秒内从(R1,C1)走到(R2,C2)所能选择的路径总数，FJ希望有一个程序来帮他计算...
02014年4月4日3,972递推与动规

「BZOJ2287」[POJ Challenge] 消失之物
Description ftiasch有 N 个物品,体积分别是 W1, W2,..., WN。由于她的疏忽,第 i 个物品丢失了。“要使用剩下的 N -1物品装满容积为 x 的背包，有几种方法呢？”--这是经典的问题了。她把答案记为 Count(i,x) ，想要得到所有1<=i<=N,1<=x<=M的 Count(i,x) 表格。 Input 第1行：两个整数 N (1≤ N ≤2×103)和 M (1≤ M ≤2×103)，物品的数量和最大的容积。第2...
22014年4月2日6,077背包动规
「POJ3107」Godfather
DescriptionLastyearsChicagowasfullofgangsterfightsandstrangemurders.Thechiefofthepolicegotreallytiredofallthesecrimes,anddecidedtoarrestthemafialeaders.Unfortunately,thestructureofChicagomafiaisrathercomplicated.Thereare n personsknowntoberelatedtomafia.Thepolicehavetracedtheiractivityforsometime,andknowthatsomeofthemarecommunicatingwitheachother.Basedonthedatacollected,thechiefofthepol...
12014年4月1日4,807树形动规
「POJ1655」Balancing Act
DescriptionConsideratreeTwithN(1<=N<=20,000)nodesnumbered1...N.Deletinganynodefromthetreeyieldsaforest:acollectionofoneormoretrees.DefinethebalanceofanodetobethesizeofthelargesttreeintheforestTcreatedbydeletingthatnodefromT.Forexample,considerthetree:Deletingnode4yieldstwotreeswhosemembernodesare{5}and{1,2,3,6,7}.Thelargerofthesetwotreeshasfivenodes,thusthebalanceofnode4isfive.D...
12014年4月1日4,343树形动规
[FJOI2014] 石子合并问题
问题描述有n堆石子，每堆1个，要合并成一堆，规定每次可以任意选两堆合并成新的一堆，两堆中较少的石子数记为该次合并的得分。输入n输出最大得分样例输入7样例输出9O（n）做法[crayon-6770b21d21f0d074160538/]O（nlogn）堆ndsf神犇秒杀[crayon-6770b21d21f16306764710/] ...
22014年3月31日6,640递推与动规,堆
「cogs754」[USACO Open09] 滑雪训练
农夫约翰想带着他的奶牛Bessie去佛罗里达滑雪，可是，Bessie的滑雪技术真是太差了。她了解到滑雪学校全天提供滑雪课程，共有S(0<=S<=100)个滑雪课程可供选择，课程i从时间M_i(1<=M_i<=10,000)开始，持续时间为L_i(1<=L_i<=10,000)，学完该课程滑雪水平将提升至A_i(1<=A_i<=100)，注意：滑雪水平的提升是绝对的，而不是累加的。此外Bessie还买了一张滑雪练习场的地图，从图中可以看到练习场每个...
02014年3月31日3,414递推与动规
「BZOJ1609」[Usaco2008 Feb] Eating Together麻烦的聚餐
Description为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。第i头奶牛有一张标明她用餐批次D_i(1<=D_i<=3)的卡片。虽然所有N(1<=N<=30,000)头奶牛排成了很整齐的队伍但谁都看得出来，卡...
02014年3月29日3,925递推与动规
「BZOJ1625」[Usaco2007 Dec] 宝石手镯
Description贝茜在珠宝店闲逛时，买到了一个中意的手镯。很自然地，她想从她收集的N(1<=N<=3,402)块宝石中选出最好的那些镶在手镯上。对于第i块宝石，它的重量为W_i(1<=W_i<=400)，并且贝茜知道它在镶上手镯后能为自己增加的魅力值D_i(1<=D_i<=100)。由于贝茜只能忍受重量不超过M(1<=M<=12,880)的手镯，她可能无法把所有喜欢的宝石都镶上。于是贝茜找到了你，告诉了你她所有宝石的属性以及她能忍...
02014年3月28日3,449背包动规
「POJ3093」Margaritas on the River Walk
DescriptionOneofthemorepopularactivitiesinSanAntonioistoenjoymargaritasintheparkalongtheriverknowasthe RiverWalk.MargaritasmaybepurchasedatmanyestablishmentsalongtheRiverWalkfromfancyhotelsto Joe’sTacoandMargarita stand.(TheproblemisnottofindouthowJoegotaliquorlicense.ThatinvolvesTexaspoliticsandthusismuchtoodifficultforanACMcontestproblem.)Thepricesofthemargaritasvarydepen...
02014年3月28日2,691背包动规
「BZOJ1618」[Usaco2008 Nov] Buying Hay 购买干草
Description 约翰的干草库存已经告罄，他打算为奶牛们采购日(1≤日≤50000)磅干草．他知道N(1≤N≤100)个干草公司，现在用1到N给它们编号．第i个公司卖的干草包重量为Pi(1≤Pi≤5000)磅，需要的开销为Ci(l≤Ci≤5000)美元．每个干草公司的货源都十分充足，可以卖出无限多的干草包．帮助约翰找到最小的开销来满足需要，即采购到至少H磅干草．Input 第1行输入N和日，之后N行每行输入一个P...
12014年3月28日4,319背包动规
「hdu2294」Pendant
ProblemDescriptionOnSaintValentine'sDay,AleximaginedtopresentaspecialpendanttohisgirlfriendmadebyKkindofpearls.Thependantisactuallyastringofpearls,anditslengthisdefinedasthenumberofpearlsinit.Asisknowntoall,Alexisveryrich,andhehasNpearlsofeachkind.Pendantcanbetoldapartaccordingtopermutationofitspearls.Nowhewantstoknowhowmanykindofpendantcanhemade,withlengthbetween1andN.Ofcour...
02014年3月27日3,041递推与动规,矩阵乘法
「BZOJ1725」[Usaco2006 Nov] Corn Fields牧场的安排
DescriptionFarmerJohn新买了一块长方形的牧场，这块牧场被划分成M列N行(1<=M<=12;1<=N<=12)，每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当的贫瘠，不能用来放牧。并且，奶牛们喜欢独占一块草地的感觉，于是FJ不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。当然，FJ还没有决定在哪些土地上种草。作为一个好奇的农场主...
42014年3月26日4,504状压动规