• 最大连续子串和问题

    最大连续子串和问题

    题目描述给定有n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列连续的子段和的最大值。如果该序列的所有元素都是负整数时定义其最大子段和为0。例如,当(a1,a2,a3,a4,a5)=(-5,11,-4,13,-4-2)时,最大子段和为11+(-4)+13=20。输入输入数据有T组测试数据。测试数据的数目(T)在输入的第一行给出。每组测试数据有两行:第一行整数个数N,第二行为N个整数,每个整数之间用一空格隔开。输出对于每组数据,输出一行,为最大连续...

    02013年11月28日1,304递推与动规
  • NOIP2007守望者的逃离

    NOIP2007守望者的逃离

    题目描述恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵,率深藏在海底的那加企图叛变:守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去,到那时,刀上的所有人都会遇难:守望者的跑步速度,为17m/s,以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点...

    02013年11月28日2,595递推与动规
  • NOIP2000方格取数

    NOIP2000方格取数

    题目描述设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例): 某人从图的左上角的A点出发,可以向下行走,也可以向右走,直到到达右下角的B点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。此人从A点到B点共走两次,试找出2条这样的路径,使得取得的数之和为最大。 输入输入的第一行为一个整数N(表示N*N的方格图),接下来的每...

    02013年11月27日1,673递推与动规
  • NOIP2004合唱队形

    NOIP2004合唱队形

    题目描述    N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。    合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,  则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。    你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。输入 ...

    02013年11月26日1,268递推与动规
  • 【tyvj1091】等差数列

    【tyvj1091】等差数列

    题目描述等差数列的定义是一个数列S,它满足了(S[i]-S[i-1]) = d (i>1)。显然的一个单独的数字或者两个数字也可以形成一个等差数列。经过一定的学习小C发现这个问题太简单了,等差数列的和不就是(Sn+S1)*n/2?因为这个问题实在是太简单了,小C不屑于去解决它。这让小C的老师愤怒了,他就找了另外一个问题来问他。小C的老师给了他一个长度为N的数字序列,每个位置有一个整数,他需要小C帮他找到这个数字序列里面有...

    02013年11月25日1,091递推与动规
  • 【tyvj1015】公路乘车

    【tyvj1015】公路乘车

    题目描述一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。 没有一辆车子行驶超过10公里,一个顾客打算行驶n公里(1<=n<=100),它可以通过无限次的换车来完成旅程。最后要求费用最少。输入 第一行十个整数分别表示行走1到10公里的费用(<=500)。注意这些数并无实际的经济意义,即行驶10公里费用可能比行驶一公里少。    第二行一个整数n表示,旅客的...

    02013年11月25日1,169背包动规
  • 【rqnoj272】马棚问题

    【rqnoj272】马棚问题

    题目描述每天,小明和他的马外出,然后他们一边跑一边玩耍。当他们结束的时候,必须带所有的马返回马棚,小明有K个马棚。他把他的马排成一排然后跟随它走向马棚,因为他们非常疲劳,小明不想让他的马做过多的移动。因此他想了一个办法:将马按照顺序放在马棚中,后面的马放的马棚的序号不会大于前面的马放的马棚的序号。而且,他不想他的K个马棚中任何一个空置,也不想任何一匹马在外面。已知共有黑、白两种马,而且它们相处得并...

    02013年11月25日1,395递推与动规
  • 【tyvj1048】田忌赛马

    【tyvj1048】田忌赛马

    题目描述    中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了,他们各派出N匹马,每场比赛,输的一方将要给赢的一方200两黄金,如果是平局的话,双方都不必拿出钱。现在每匹马的速度值是固定而且已知的,而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马,才能赢取最多的钱?输入第一行为一个正整数n (n <= 1000) ,表示双方马的数量。第二行有N个整数表示田忌...

    32013年11月23日2,904递推与动规,贪心
  • 拦截导弹

    拦截导弹

    题目描述       M-78星云上有丰富的矿产资源,而njn极想掠夺其资源,2月30日njn终于发动了对M-78星云的侵略战争。众多正义和平之士在jun的带领下来到M-78星云协助当地居民抵抗外来侵略。由于njn对M-78星云的战争迟迟不能结束,所以,njn终于使出杀手锏:发射导弹,攻击M-78星云。幸好jun事先已在njn的军营中安插间谍pzy。pzy不负众望,终于秘密的获得了njn要发射的n个导弹的高度。获的导弹机密后,jun又面临一个严峻的...

    02013年11月21日1,428递推与动规
  • 机器分配

    机器分配

    题目描述描述Description                                                                            总公司拥有高效生产设备M台,准备分给下属的N个公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M<=15,N<=10。分配原则:每个公司有权获得任意数...

    02013年11月21日1,471背包动规
  • 硬币找零

    硬币找零

    题目描述设有n种(n<=20)不同面值的硬币,各硬币的面值存于数组T[1..N]中,数据中至少有一枚硬币面值为1,现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数不限,请计算找出钱数m(1<=m<=10000)的最少硬币个数。输入:第一行为n种硬币和要找的钱数m;第二行为分别为n种硬币的面值t1,t2…tn输出:最小的硬币个数样例输入[crayon-5a5e009211ae2379272305/]样例输出[crayon-5a5e009211af0918666771/]代码[crayon-...

    02013年11月21日1,365背包动规
  • 导弹拦截问题系列

    导弹拦截问题系列

    导弹问题1题目描述       某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹?该导...

    02013年11月21日1,842递推与动规