递推与动规 - Page 12

「BZOJ1806」[IOI2007] Miners 矿工配餐
Description现有两个煤矿，每个煤矿都雇用一组矿工。采煤工作很辛苦，所以矿工们需要良好饮食。每当一辆食品车到达煤矿时，矿工们便会产出一定数量的煤。有三种类型的食品车：肉车，鱼车和面包车。矿工们喜欢变化的食谱。如果提供的食品能够不断变化，他们的产煤量将会增加。每当一个新的食品车到达煤矿时，矿工们就会比较这种新的食品和前两次（或者少于两次，如果前面运送食品的次数不足两次）的食品，并且：•如果这几次食品车...
02014年7月10日4,088递推与动规

「NOIP模拟赛」笨笨当粉刷匠
笨笨太好玩了，农田荒芜了，彩奖用光了，笨笨只好到处找工作，笨笨找到了一份粉刷匠的工作。笨笨有n条木板需要被粉刷。每条木板被分成m个格子，每个格子要被刷成红色或蓝色。笨笨每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色，已知每个格子最多只能被粉刷一次。如果笨笨只能粉刷t次，他最多能正确粉刷多少格子。一个格子如果未被粉刷或被粉刷成错误颜色，就算粉刷错误。「输入格式」第一行三个数n，m，t；接下来...
02014年7月8日3,990递推与动规,背包动规
「BZOJ1492」[NOI2007] 货币兑换Cash
DescriptionInput第一行两个正整数N、S，分别表示小Y能预知的天数以及初始时拥有的钱数。接下来N行，第K行三个实数AK、BK、RateK，意义如题目中所述Output只有一个实数MaxProfit，表示第N天的操作结束时能够获得的最大的金钱数目。答案保留3位小数。SampleInput3100111122223SampleOutput225.000HINT测试数据设计使得精度误差不会超过10-7。对于40%的测试数据，满足N≤10；对于60%的测试数据，满足N≤1...
102014年6月18日10,910递推与动规
「泉七培训 – 郑予凡」子集
炫教的题解：为叙述方便，我们不妨设S={-n,-n+1,...,n}。本题就转化为求解∑χ(A)。其中求和式取遍S的k元子集A，而χ(A)当A的元素之和为0时返回1，否则返回0。我们给出一些在比赛过程中解决本题的常见的算法。「算法1：枚举」顾名思义，这个算法直接枚举所有可能的A，然后逐一考察χ(A)。期望得分：10「算法2：动态规划」记dp[a][b][c]为“从-n到n，当前已枚举到a∈S并已考虑完其是否在A中，已经确定了b个数在集合A中，...
02014年6月14日3,388递推与动规
「BZOJ1801」[Ahoi2009] chess 中国象棋
Description在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.Input一行包含两个整数N，M，中间用空格分开.Output输出所有的方案数，由于值比较大，输出其mod9999973SampleInput13SampleOutput7HINT除了在3个格子中都放满炮的的情况外，其它的都可以.100%的数据中N,M不超过10050%的数据中，N,M至少有一个数不超过83...
22014年6月7日3,645递推与动规
「CF439D」Devu and his Brother
Devuandhisbrotherloveeachotheralot.Astheyaresupergeeks,theyonlyliketoplaywitharrays.Theyaregiventwoarrays a and b bytheirfather.Thearray a isgiventoDevuand b tohisbrother.AsDevuisreallyanaughtykid,hewantstheminimumvalueofhisarray a shouldbeatleastasmuchasthemaximumvalueofhisbrother'sarray b.NowyouhavetohelpDevuinachievingthiscondition.Youcanperformmultipleoperationsonthearrays...
02014年6月5日2,873递推与动规
「NOIP模拟赛」某种数列问题
题目描述众所周知，czy97有无数的妹子(阿掉！>_<)，而且他还有很多恶趣味的问题，继上次纠结于一排妹子的排法以后，今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的妹子站成一排，然后对于每个妹子有一个美丽度，当然美丽度越大越好，chenzeyu97妹子很多，但是质量上不容乐观，经常出现很多美丽度为负数的妹子(喜闻乐见)，czy97希望从一排妹子里找出3队连续的妹子，使她们的美丽度和最大。注意，一...
02014年6月1日3,742递推与动规
「BZOJ1592」[Usaco2008 Feb] Making the Grade 路面修整
DescriptionFJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能同时出现在修好的路中。整条路被分成了N段，N个整数A_1,...,A_N(1<=N<=2,000)依次描述了每一段路的高度(0<=A_i<=1,000,000,000)。FJ希望找到一个恰好含N个元素的不上升或不下降序列B_1,...,B_N，作为修过的路中每个路段的高度。由于将每一段路...
72014年5月29日4,321递推与动规
「BZOJ1537」[POI2005] Aut – The Bus
DescriptionByteCity的街道形成了一个标准的棋盘网络–他们要么是北南走向要么就是西东走向.北南走向的路口从1到n编号,西东走向的路从1到m编号.每个路口用两个数(i,j)表示(1<=i<=n,1<=j<=m).ByteCity里有一条公交线,在某一些路口设置了公交站点.公交车从(1,1)发车,在(n,m)结束.公交车只能往北或往东走.现在有一些乘客在某些站点等车.公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.I...
02014年5月28日3,963递推与动规,树状数组
「BZOJ2442」[Usaco2011 Open] 修剪草坪
Description在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N(1<=N<=100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，奶牛i的效率为E_i(0<=E_i<=1,000,000,000)。靠近的奶牛们很熟悉，因此，如果FJ安排超过K只连续的奶牛，...
92014年5月24日7,203递推与动规,单调队列
「BZOJ1642」[Usaco2007 Nov] Milking Time 挤奶时间
Description贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的N(1≤N≤1,000,000)个小时，标记为0..N-1。FarmerJohn计划好了M(1≤M≤1,000)个可以挤奶的时间段。每个时间段有一个开始时间(0≤开始时间≤N),和一个结束时间(开始时间<结束时间≤N),和一个产量(1≤产量≤1,000,000)表示可以从贝茜挤奶的数量。FarmerJohn从分别从开始时间挤奶，到结束时间为止。每次挤奶...
02014年5月23日3,191递推与动规
「BZOJ1679」[Usaco2005 Jan] Moo Volume 牛的呼声
DescriptionFarmerJohnhasreceivedanoisecomplaintfromhisneighbor,FarmerBob,statingthathiscowsaremakingtoomuchnoise.FJ'sNcows(1<=N<=10,000)allgrazeatvariouslocationsonalongone-dimensionalpasture.Thecowsareverychattyanimals.Everypairofcowssimultaneouslycarriesonaconversation(soeverycowissimultaneouslyMOOingatalloftheN-1othercows).WhencowiMOOsatcowj,thevolumeofthisMOOmustbee...
02014年5月23日3,658递推与动规