贪心 - Page 13 - hzwer.com

「BZOJ1827」[Usaco2010 Mar] gather 奶牛大集会
DescriptionBessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1<=A_i<=N;1<=B_i<=N),长度为L_i(1<=L_i<=1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居...
02014年5月19日4,212贪心,树形动规

「BZOJ2697」特技飞行
Description神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间，每个单位时间可以进行一项特技动作，可选的动作有K种，每种动作有一个刺激程度Ci。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间)*Ci，若为第一次进行该动作，价值为0。安排一种方案，使得总价值最大。Input　　第一行，两个数，N和K，如上所述；第二行，K个正整数，表示K种动作的Ci值。Output　　仅...
02014年5月8日3,757贪心
「BZOJ1150」[CTSC2007] 数据备份Backup
Description Input输入的第一行包含整数n和k，其中n（2≤n≤100000）表示办公楼的数目，k（1≤k≤n/2）表示可利用的网络电缆的数目。接下来的n行每行仅包含一个整数（0≤s≤1000000000）,表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。Output输出应由一个正整数组成，给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。SampleInput52134612SampleOutput4HINT上面的样例输入给出...
02014年5月7日7,779贪心,堆,链表
「BZOJ2288」「POJ Challenge」生日礼物
Descriptionftiasch18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2,..., AN.她被允许选择不超过 M 个连续的部分作为自己的生日礼物。自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？Input第1行，两个整数 N (1≤ N ≤105)和 M (0≤ M ≤105),序列的长度和可以选择的部分。第2行， N 个整数 A1, A2,..., AN (0≤|Ai|≤104),序列。Output一个整数，最大的和。SampleI...
12014年5月7日7,611堆,贪心,链表
「CF425A」Sereja and Swaps
Asusual,Serejahasarray a,itselementsareintegers: a[1], a[2], ..., a[n].Let'sintroducenotation:Aswapoperationisthefollowingsequenceofactions:choosetwoindexes i, j (i ≠ j);performassignments tmp = a[i], a[i] = a[j], a[j] = tmp.Whatmaximumvalueoffunction m(a) canSerejagetifheisallowedtoperformatmost k swapoperations?InputThefirstlinecontainstwointegers n and k (1 ...
02014年4月28日3,465贪心
任务调度
来源：http://nnsznoi.openjudge.cn/greedy/0014/ Description一个单位时间任务是一个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1,结束于时间2;……。单处理器上具有期限和罚款的单位时间任务调度问题的输入如下:1.包含n个单位时间任务的集合S={...
02014年4月25日3,519贪心
「CF413C」Jeopardy!
'Jeopardy!'isanintellectualgamewhereplayersanswerquestionsandearnpoints.CompanyQconductsasimplified'Jeopardy!'tournamentamongthebestITcompanies.Byaluckycoincidence,theoldrivalsmadeittothefinals:companyR1andcompanyR2.Thefinalswillhave n questions, m ofthemareauctionquestionsand n - m ofthemareregularquestions.Eachquestionhasaprice.Thepriceofthe i-thquestionis ai points.Durin...
02014年4月20日2,652贪心
「BZOJ1689」[Usaco2005 Open] Muddy roads 泥泞的路
DescriptionFarmerJohnhasaproblem:thedirtroadfromhisfarmtotownhassufferedintherecentrainstormsandnowcontains(1<=N<=10,000)mudpools.FarmerJohnhasacollectionofwoodenplanksoflengthLthathecanusetobridgethesemudpools.Hecanoverlapplanksandtheendsdonotneedtobeanchoredontheground.However,hemustcovereachpoolcompletely.Giventhemudpools,helpFJfigureouttheminimumnumberofplanksheneedsinorderto...
02014年4月16日3,490贪心
「BZOJ1572」[Usaco2009 Open] 工作安排Job
DescriptionFarmerJohn有太多的工作要做啊！！！！！！！！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从0时刻开始，有1000000000个单位时间（！）。在任一时刻，他都可以选择编号1~N的N(1<=N<=100000)项工作中的任意一项工作来完成。因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。对于第i个工作，有一个...
02014年3月30日3,755贪心,堆
最大最小差
题目描述现在有N个正整数，每一次去掉其中2个数a和b，然后加入一个数a*b+1，这样最后只剩下一个数p。要求求出最大的p记为maxp，最小的p记为minp，和他们的差K=maxp-minp。编程任务：对于给定的数列，编程计算出它的max,min和K。输入输入（标准输入）：第一行是数列的长度N（不超过2000），以下N行，每行一个正整数（不超过9位）。输出输出（标准输出）：输出一共三行，每行一个整数，依次为max,min,K。样例输入211样例输出22...
02014年3月29日4,036贪心,堆
「BZOJ1724」[Usaco2006 Nov] Fence Repair切割木板
DescriptionFarmerJohn想修理牧场栅栏的某些小段。为此，他需要N(1<=N<=20,000)块特定长度的木板，第i块木板的长度为Li(1<=Li<=50,000)。然后，FJ去买了一块很长的木板，它的长度正好等于所有需要的木板的长度和。接下来的工作，当然是把它锯成需要的长度。FJ忽略所有切割时的损失——你也应当忽略它。FJ郁闷地发现，他并没有锯子来把这块长木板锯开。于是他把这块长木板带到了FarmerDon的农场，想向F...
02014年3月28日5,062贪心,堆
「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,549贪心,背包动规