递推与动规 - Page 16

「vijos1055」奶牛浴场
描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮...
12014年1月6日4,044递推与动规

「BZOJ1270」[BJWc2008] 雷涛的小猫
Description InputOutputSampleInput3102314106359789545369SampleOutput8HINT代码比较水的动规题。。[crayon-67400e9626799820195280/]
12014年1月6日4,652递推与动规
「BZOJ1003」[ZJOI2006] 物流运输trans
Description物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使...
12014年1月6日8,047递推与动规,spfa
「JoyOI1051」选课
题目描述学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。　　在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操...
32014年1月2日4,466递推与动规
「vijos1470」教主的后花园
描述教主有着一个环形的花园，他想在花园周围均匀地种上n棵树，但是教主花园的土壤很特别，每个位置适合种的树都不一样，一些树可能会因为不适合这个位置的土壤而损失观赏价值。教主最喜欢3种树，这3种树的高度分别为10，20，30。教主希望这一圈树种得有层次感，所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低，并且在此条件下，教主想要你设计出一套方案，使得观赏价值之和最高。格式输入格式输入的第1行为一个正整数...
02013年12月29日2,709递推与动规
牛奶容器
来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1146题目描述农民保罗有如下型号的牛奶容器:10加伦，2加伦，1 加伦，1/4加伦，1/8加伦，1/16加伦。请您帮他编写一个程序，能计算保罗用这些容器取X加伦牛奶共有多少不同方法。在所有的数据中，X都是整数且(1<=X<=100)。输入输入数据中有多组测试数据，每组测试数组仅有一行，包含一个整数x。最后一行以0表示结束。输出对于每组数据，输出一行，为保罗用这...
32013年12月19日3,274递推与动规
「vijos1111」小胖的水果
描述xuzhenyi到大同水果店去买水果，但老板huyichen告诉他每次只能买一种，但是xuzhenyi想吃两种，于是在讨价还价之后，huyichen说只要xuzhenyi能把他想要的两种水果合并成一种，就能成功。你能帮他吗？输入格式输入文件包含两个要组合的水果名字。所有的名字最多有100个字母。(有若干行）输出格式对每一组测试数据，打印出一个最短的组合长度.样例输入[crayon-67400e962953b530034718/]样例输出[crayon-67400e9629547030173478/]代...
02013年12月19日2,624递推与动规
NOIP2010乌龟棋
描述小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每...
02013年12月4日6,354递推与动规
最大串和
题目描述有n个整数排成一圈，现在要从中找出连续的一段数串，使得这串数的和最大。输入（标准输入）：第一行一个整数m,表示有m组数据。每组数据第一行一个整数n(n<=10^6)。第二行有n个整数，用空格隔开。输出（标准输出）：对于每组数据输出一行三个整数p,x,y。表示从x到y的数串有最大和p。在多解情况下要求x最小，x相同的情况下y最小。保证p在长整范围。Input:1312-9output:312代码[crayon-67400e962a1bf945709992/]好像是因为...
02013年12月2日3,839递推与动规
「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日5,216递推与动规
「JoyOI1050」最长公共子序列
题目描述一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad",顺次选1，3，5个字符就构成子串"cad",现给定两个字符串，求它们的最长共公子串。输入第一行两个字符串用空格分开。输出最长子串的长度。样例输入abccdaecd样例输出3提示两个串的长度均小于2000 代码[crayon-67400e962ac42467067200/] ...
02013年12月1日3,799递推与动规
「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日4,618递推与动规