• 最大连续子串和问题

    最大连续子串和问题

    题目描述给定有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,562递推与动规
  • NOIP2007守望者的逃离

    NOIP2007守望者的逃离

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

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

    NOIP2000方格取数

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

    02013年11月27日2,018递推与动规
  • 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,604递推与动规
  • 「JoyOI1091」等差数列

    「JoyOI1091」等差数列

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

    02013年11月25日1,337递推与动规
  • 「RQNOJ272」马棚问题

    「RQNOJ272」马棚问题

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

    02013年11月25日1,711递推与动规
  • 「JoyOI1048」田忌赛马

    「JoyOI1048」田忌赛马

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

    42013年11月23日4,128递推与动规,贪心
  • 拦截导弹

    拦截导弹

    题目描述       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,719递推与动规
  • 导弹拦截问题系列

    导弹拦截问题系列

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

    02013年11月21日2,446递推与动规
  • 城市交通

    城市交通

    题目描述有n个城市,编号1~n,有些城市之间有路相连,有些则没有,有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市,问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少?输入输入格式:先输入一个n,表示城市数,n<100。下面的n行,是一个n*n的邻接矩阵map[1..n,1..n]。map[i,j]=0,表示城市i和城市j之间没有路相连,否则为两者之间的距离。输出输出格式:一个数,表示从城市1走到城市n的最短距离...

    02013年11月21日1,686递推与动规
  • 数字三角形系列

    数字三角形系列

    数字三角形题目描述示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。 每一步可沿左斜线向下或右斜线向下走; 1<三角形行数<25; 三角形中的数字为整数<1000;输入第一行为N,表示有N行后面N行表示三角形每条路的路径权输出路径所经过的数字的总和最大的答案样例输入5738810274445265样例输出30提示 搜索80分,记忆化搜索AC 代码[crayon-5bc726553...

    12013年11月21日3,980递推与动规
  • 「RQNOJ166」免费午餐

    「RQNOJ166」免费午餐

    题目描述为了增加顾客,Sally的店铺决定提供免费午餐,顿时门庭若市,但是不久Sally的原材料不足了….因此Sally决定公布一项决定:凡是来本店吃免费午餐的,一天吃能吃一次,吃的数量必须比上一次吃的少,点的必须在上一次后面,且免费午餐将只有N个种类任君选择,为了能吃到最多的免费午餐,你将如何安排每日吃的数量呢?输入格式第一行一个数N,表示免费午餐的种类(0<=N<=100000)第二行N个数,表示每个免费午餐的数量(0<...

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