背包动规 - Page 2

「BZOJ1296」[SCOI2009] 粉刷匠
Descriptionwindy有N条木板需要被粉刷。每条木板被分为M个格子。每个格子要被刷成红色或蓝色。windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷T次，他最多能正确粉刷多少格子？一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。Input输入文件paint.in第一行包含三个整数，NMT。接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色...
12014年5月20日5,358递推与动规,背包动规

「JoyOI1608」小熊分糖
背景BackgroundAndyBear 生日模拟赛第二题描述Description晴朗的上午，小熊BIBO抱着一罐糖，出去找好朋友，两只小兔子。从小熊家出来，穿过小树林，在一个有向日葵的路口向右拐，这就是小兔子家了。小熊BIBO见到好朋友，开心的不得了，BIBO要做的第一件事，是分糖，因为大熊说过，好东西是不可以独享的。糖罐里有N颗糖，小熊BIBO要挑出m颗来给两只小兔子，剩下的留着自己吃。对于这n颗糖中的每一颗，这两...
02014年5月17日4,052背包动规
「BZOJ2748」[HAOI2012] 音量调节
Description一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件...
02014年4月30日5,179背包动规
「CF417A」Elimination
Thefinalistsofthe"RussianCodeCup"competitionin2214willbetheparticipantswhowininoneoftheeliminationrounds.Theeliminationroundsaredividedintomainandadditional.Eachofthemaineliminationroundsconsistsof c problems,thewinnersoftheroundarethefirst n peopleintheratinglist.Eachoftheadditionaleliminationroundsconsistsof d problems.Thewinneroftheadditionalroundisoneperson.Besides, k winnerso...
02014年4月19日2,838背包动规
「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,051背包动规
「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,425背包动规
「POJ3093」Margaritas on the River Walk
DescriptionOneofthemorepopularactivitiesinSanAntonioistoenjoymargaritasintheparkalongtheriverknowasthe RiverWalk.MargaritasmaybepurchasedatmanyestablishmentsalongtheRiverWalkfromfancyhotelsto Joe’sTacoandMargarita stand.(TheproblemisnottofindouthowJoegotaliquorlicense.ThatinvolvesTexaspoliticsandthusismuchtoodifficultforanACMcontestproblem.)Thepricesofthemargaritasvarydepen...
02014年3月28日2,674背包动规
「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,297背包动规
「BZOJ1606」[Usaco2008 Dec] Hay For Sale 购买干草
Description 约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草．顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，他最多可以运回多少体积的干草呢？Input 第1行输入C和H，之后H行一行输入一个Vi．Output 最多的可买干草体积．SampleInput73//总体积为7,用3个物品来背包265T...
02014年3月24日4,503背包动规
「BZOJ1708」[Usaco2007 Oct] Money奶牛的硬币(货币系统)
Description在创立了她们自己的政权之后，奶牛们决定推广新的货币系统。在强烈的叛逆心理的驱使下，她们准备使用奇怪的面值。在传统的货币系统中，硬币的面值通常是1，5，10，20或25，50，以及100单位的货币，有时为了更方便地交易，会发行面值为2单位的硬币。奶牛们想知道，对于一个给定的货币系统，如果需要正好凑出一定数量的钱，会有多少种不同的方法。比如说，你手上有无限多个面值为{1，2，5，10，...}的硬币，并且打算凑出...
12014年3月23日4,139背包动规
「POJ2392」Space Elevator
DescriptionThecowsaregoingtospace!Theyplantoachieveorbitbybuildingasortofspaceelevator:agianttowerofblocks.TheyhaveK(1<=K<=400)differenttypesofblockswithwhichtobuildthetower.Eachblockoftypeihasheighth_i(1<=h_i<=100)andisavailableinquantityc_i(1<=c_i<=10).Duetopossibledamagecausedbycosmicrays,nopartofablockoftypeicanexceedamaximumaltitudea_i(1<=a_i<=40000).Helptheco...
02014年3月18日3,525贪心,背包动规
「NOIP模拟赛」灵魂分流药剂
问题描述皇家炼金师赫布瑞姆刚刚发明了一种用来折磨一切生物的新产品，灵魂分流药剂。灵魂分流药剂的妙处在于能够给服用者带来巨大的痛苦，但是却不会让服用者死去，而且可以阻止服用者的自杀。用它来对付敢于反对希尔瓦娜斯女王的狂徒们，简直是太精妙了。最近，侦察兵抓获了一个来自暴风城的人类探子，希尔瓦娜斯女王命令你用最痛苦的手段来折磨他。你拥有N瓶药剂，按照成分配比的不同装在M个箱子中。每瓶药剂的有以下参...
12014年3月7日2,736背包动规