• 「BZOJ1827」[Usaco2010 Mar] gather 奶牛大集会

    「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日1,977贪心,树形动规
  • 「BZOJ2697」特技飞行

    「BZOJ2697」特技飞行

    Description神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间,每个单位时间可以进行一项特技动作,可选的动作有K种,每种动作有一个刺激程度Ci。如果连续进行相同的动作,乘客会感到厌倦,所以定义某次动作的价值为(距上次该动作的时间)*Ci,若为第一次进行该动作,价值为0。安排一种方案,使得总价值最大。Input  第一行,两个数,N和K,如上所述;第二行,K个正整数,表示K种动作的Ci值。Output  仅...

    02014年5月8日1,731贪心
  • 「BZOJ1150」[CTSC2007] 数据备份Backup

    「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日3,894,贪心,链表
  • 「BZOJ2288」「POJ Challenge」生日礼物

    「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...

    02014年5月7日2,952贪心,,链表
  • 「CF425A」Sereja and Swaps

    「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日1,232贪心
  • 任务调度

    任务调度

    来源:http://nnsznoi.openjudge.cn/greedy/0014/ Description一个单位时间任务是一个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1,结束于时间2;……。单处理器上具有期限和罚款的单位时间任务调度问题的输入如下:1.包含n个单位时间任务的集合S={...

    02014年4月25日1,282贪心
  • 「CF413C」Jeopardy!

    「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日1,054贪心
  • 「BZOJ1689」[Usaco2005 Open] Muddy roads 泥泞的路

    「BZOJ1689」[Usaco2005 Open] Muddy roads 泥泞的路

    DescriptionFarmerJohnhasaproblem:thedirtroadfromhisfarmtotownhassufferedintherecentrainstormsandnowcontains(1<=N<=10,000)mudpools.FarmerJohnhasacollectionofwoodenplanksoflengthLthathecanusetobridgethesemudpools.Hecanoverlapplanksandtheendsdonotneedtobeanchoredontheground.However,hemustcovereachpoolcompletely.Giventhemudpools,helpFJfigureouttheminimumnumberofplanksheneedsinorderto...

    02014年4月16日1,674贪心
  • 「BZOJ1572」[Usaco2009 Open] 工作安排Job

    「BZOJ1572」[Usaco2009 Open] 工作安排Job

    DescriptionFarmerJohn有太多的工作要做啊!!!!!!!!为了让农场高效运转,他必须靠他的工作赚钱,每项工作花一个单位时间。他的工作日从0时刻开始,有1000000000个单位时间(!)。在任一时刻,他都可以选择编号1~N的N(1<=N<=100000)项工作中的任意一项工作来完成。因为他在每个单位时间里只能做一个工作,而每项工作又有一个截止日期,所以他很难有时间完成所有N个工作,虽然还是有可能。对于第i个工作,有一个...

    02014年3月30日1,858,贪心
  • 最大最小差

    最大最小差

    题目描述现在有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日1,536贪心,
  • 「BZOJ1724」[Usaco2006 Nov] Fence Repair切割木板

    「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日2,331贪心,
  • 「POJ2392」Space Elevator

    「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日1,440贪心,背包动规