• 「vijos1057」盖房子

    「vijos1057」盖房子

    描述永恒の灵魂最近得到了面积为n*m的一大块土地(高兴ING^_^),他想在这块土地上建造一所房子,这个房子必须是正方形的。但是,这块土地并非十全十美,上面有很多不平坦的地方(也可以叫瑕疵)。这些瑕疵十分恶心,以至于根本不能在上面盖一砖一瓦。他希望找到一块最大的正方形无瑕疵土地来盖房子。不过,这并不是什么难题,永恒の灵魂在10分钟内就轻松解决了这个问题。现在,您也来试试吧。输入格式输入文件第一行为两个整数n,m(...

    02013年12月19日1,815区间动规
  • 「vijos1111」小胖的水果

    「vijos1111」小胖的水果

    描述xuzhenyi到大同水果店去买水果,但老板huyichen告诉他每次只能买一种,但是xuzhenyi想吃两种,于是在讨价还价之后,huyichen说只要xuzhenyi能把他想要的两种水果合并成一种,就能成功。你能帮他吗?输入格式输入文件包含两个要组合的水果名字。所有的名字最多有100个字母。(有若干行)输出格式对每一组测试数据,打印出一个最短的组合长度.样例输入[crayon-5ade7f50a2806668906985/]样例输出[crayon-5ade7f50a280d666137909/]代...

    02013年12月19日1,096递推与动规
  • 「CODEVS1380」没有上司的舞会

    「CODEVS1380」没有上司的舞会

    此题同「bzoj2060」[Usaco2010Nov]VisitingCows拜访奶牛题目描述Ural大学有N个职员,编号为1~N。他们有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会,要求与会职员的快乐指数最大。但是,没有职员愿和直接上司一起与会。输入第一行一个整数N。(1<=N<=6000)接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)接...

    32013年12月7日2,268树形动规
  • NOIP2010乌龟棋

    NOIP2010乌龟棋

    描述小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中M张爬行卡片,分成4种不同的类型(M张卡片中不一定包含所有4种类型的卡片,见样例),每种类型的卡片上分别标有1、2、3、4四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每...

    02013年12月4日4,170递推与动规
  • 最大串和

    最大串和

    题目描述有n个整数排成一圈,现在要从中找出连续的一段数串,使得这串数的和最大。输入(标准输入):第一行一个整数m,表示有m组数据。每组数据第一行一个整数n(n<=10^6)。第二行有n个整数,用空格隔开。输出(标准输出):对于每组数据输出一行三个整数p,x,y。表示从x到y的数串有最大和p。在多解情况下要求x最小,x相同的情况下y最小。保证p在长整范围。Input:1312-9output:312代码[crayon-5ade7f50a35e5919133648/]好像是因为...

    02013年12月2日1,501递推与动规
  • 「RQNOJ106」最大加权矩形(最大子矩阵和问题)

    「RQNOJ106」最大加权矩形(最大子矩阵和问题)

    给定一个长度为n的一维的数组matrix[n],让求其最大matrix[i]+matrix[i+1]+...+matrix[j]=sum问题? 简单算法:穷举法先预处理map[n]表示从matrix[0]->matrix[n]的和for(inti=0ton)for(intj=i+1ton){inttmp=map[j] -map[i-1];}算法时间复杂度为O(n^2).空间额外占据O(n)。 DP算法:设max[j]为matrix[0....j]中的最大子段之和,max[j]当前只有两种情况:1)最大子段一直连续到matrix[j];(2)以matrix[j]为起点的子段...

    02013年12月2日2,405递推与动规
  • 「JoyOI1050」最长公共子序列

    「JoyOI1050」最长公共子序列

    题目描述一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad",顺次选1,3,5个字符就构成子串"cad",现给定两个字符串,求它们的最长共公子串。输入第一行两个字符串用空格分开。输出最长子串的长度。样例输入abccdaecd样例输出3提示 两个串的长度均小于2000 代码[crayon-5ade7f50a3c61021597786/] ...

    02013年12月1日1,937递推与动规
  • 「JoyOI1049」最长不下降子序列

    「JoyOI1049」最长不下降子序列

    题目描述有由n个不相同的整数组成的数列,记为:a1、a2、……、an,例如3,18,7,14,10,12,23,41,16,24。若存在i1<i2<i3<…<ie 且有a(i1)<=a(i2)<=…<=a(ie)则称为长度为e的不下降序列。如上例中3,18,23,24就是一个长度为4的不下降序列,同时也有3,7,10,12,16,24长度为6的不下降序列。输入第一行为n,表示n个数第二行n个数输出最长不下降子序列的长度样例输入3123样例输出3提示 N小于...

    12013年12月1日2,158递推与动规
  • NOIP1999拦截导弹

    NOIP1999拦截导弹

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

    02013年12月1日5,351递推与动规,贪心
  • 0 / 1背包问题

    0 / 1背包问题

    题目描述       小明就要去春游了,小明的妈妈给他买了很多好吃的,小明想把这些吃的都放进他的书包,但他很快发现,妈妈买的东西实在太多了,他必须放弃一些,但小明又希望能带尽可能多的好吃的。因此小明想请你帮他往书包里装尽可能多的好吃的。现在我们知道小明的书包最多可以装入总重量为s的物品,同时我们也知道小明妈妈给他买的每样东西的重量,现在请你从这些好吃的中选出若干装入书包中,使得装入物品的总重量正好为...

    02013年11月30日2,223背包动规,深度搜索
  • NOIP2002过河卒

    NOIP2002过河卒

    题目描述如图,A点有一个过河卒,需要走到目标B点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图C点上的马可以控制9个点(图中的P1,P2…P8和C)。卒不能通过对方马的控制点。棋盘用坐标表示,A点(0,0)、B点(n,m)(n,m为不超过20的整数,并由键盘输入),同样马的位置坐标是需要给出的(约定:C<>A,...

    02013年11月29日2,375递推与动规
  • 石子合并

    石子合并

    来源:http://218.5.5.242:9018/JudgeOnline/problem.php?id=1295[问题描述]在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小总得分。[编程任务]对于给定n堆石子,编程计算合并成一堆的最小总得分。[输入格式]输入文件的第1行是正整数n,1<=n<=1000,表示有n堆石子。...

    02013年11月29日3,486区间动规