完全背包  Description 设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。 Input 第一行：两个整数，M(背包容量，M<= 200)和N(物品数量，N<= 30)； 第2…N+1 行：每行二个整数Wi,Ui，表示每个物品的重量和价值。 Output 仅一行，一个数，表示最大总价值。 Sample Input  12 4 2 1 3 3 4 5 7 9  Sample Output 15  解题思路 这道题的方法是动态规...

竞赛得分  Description 学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分。现在要进行一次竞赛，总时间T固定，有若干类型可选择的题目，每种类型题目可选入的数量不限，每种类型题目有一个si(解答此题所得的分数)和ti(解答此题所需的时间)，现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大。 输入包括竞赛的时间,M(1 <= M <= 10000)和题目类型数目N(1 <= N <= 10000)。 后面的每一行将包括两个整数来描述一种"题型": 第一个整数说明解决这种题目能得...

购买干草  Description 约翰的干草库存已经告罄,他打算为奶牛们采购H(1≤H≤50000)磅干草,他知道N(1≤N≤100)个干草公司,现在用1到N给它们编号。第i个公司卖的干草包重量为Pi(1≤Pi≤5000)磅,需要的开销为Ci(l≤Ci≤5000)美元．每个干草公司的货源都十分充足,可以卖出无限多的干草包.帮助约翰找到最小的开销来满足需要,即采购到至少H磅干草． Input 第1行输入N和H，之后N行每行输入一个Pi和Ci． Output 最小的开销． Sample Input 2 15 3 2 5 3  Sample Output 9  解题思路 这道题也是使用完全背包的方...

货币系统  各位看官老爷们给点赞和评论吧~~Orz  Description 母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。 [In their own rebellious way]，他们对货币的数值感到好奇。 传统地，一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。 母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。 举例来说, 使用一个货币系统 {1,2,5,10,…}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。 写一个程序来计算有多少种方法用给定的货币系统来...

步步高升  Description 春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位，看到一盆叫做“步步高升”的盆竹。“步步高升，步步高升……”学习就是要一步一步来，不能急，要打好基础。在稳固的基础上才谈得上步步高升！TENSHI若有所思。她看到这盆东西好意头，于是想买下。谁知一问价钱，“不贵不贵，才２ＸＸＲＭＢ。”TENSHI差点没昏倒，囊中羞涩嘛。但是TENSHI还是很想买下来，于是她就在一旁观察。观察了一段时间，她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi元，那么他第i+1次报的价格为Wi－A或Wi －B。到了最后，TENSHI以Z元成交，高高兴兴的回家去了。  ...

公共子串  Description 设有A、B两个字符串，找出A、B共同子串，每个字符串无相同字符，可以不连续，但顺序不能颠倒。 Input 第一行字符串A 第二行字符串Ｂ Output 最长公共子串的长度. Sample Input abcfbc abfcab  Sample Output 4  解题思路 这道题其实可以用下面这幅图表示：  这里2表示输入数据里的a，4表示b，只有小部分，剩下的自己推，这里行的2与列的2相等，就是1加这个位置的左上角的数，如果不相等，就选择上面和左边最大的那个数。最后输出这个矩阵里的最大值。 动态转移方程： i f ( y [ i ] = = x [ j ]...

旅行  Description ACM队员们到Z镇游玩，Z镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成MN个区域。Z镇的名胜位于这些区域内，从上往下第i行，从左往右数第j列的区域记为D（i,j）。ACM队员们预先对这MN个区域打分V(i,j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便集合，队员们只能在某一个范围内活动。我们可以用(m1,n1)与(m2,n2)(m1<=m2，n1<=n2)表示这样一个范围：它是这些区域的集合： ，ACM队员希望他们活动区域的分值总和最大。 当然，有的队员可能一个也不去（例如，所有区域...

糖果盒  Description 一个被分为 n*m 个格子的糖果盒，第 i 行第 j 列位置的格子里面有 a [ i ][ j ] 颗糖。本来 tenshi 打算送这盒糖果给某 PPMM 的，但是就在要送出糖果盒的前一天晚上，一只极其可恶的老鼠夜袭糖果盒，有部分格子被洗劫并且穿了洞。tenshi 必须尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且 tenshi 希望保留在新糖果盒内的糖的总数尽量多。 请帮tenshi设计一个程序 计算一下新糖果盒最多能够保留多少糖果。 Input 从文件CANDY.IN读入数据。第一行有两个整数 n、m。第 i + 1 行的第 j 个数表...

勇闯黄金十二宫—射手宫  Description 第九个他们来到射手宫，身为射手座黄金圣斗士的艾尔里斯是狮子座圣斗士艾尔里亚的哥哥，他早在13年前就发现了撒加杀了真教皇，并且自己做了假教皇。然而他却被撒加***致死。现在星矢四人已经来到了射手宫。艾尔里斯的灵魂想考验一下这些圣斗士们的水平，在射手宫的墙上留下了一道题目。 “已知艾尔里斯和弟弟艾尔里亚的基因基本相同，由于基因表达起来不方便，所以就用n个数字来表示。(因为至今共发现100000种基因，所以每个数字都<=100000)兄弟之间的基因个数是相同的，就是说他们都有n个数字。且对于每个人，这n个数字互不相同。现在要求兄弟之间基因的最长...

最佳浏览路线  Description 某旅游区的街道成网格状（见图），其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路值得浏览得程度，分值从-１００到１００的整数，所有林荫道不打分。所有分值不可能全是负值。   例如下图是被打过分的某旅游区的街道图： 阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。 Inp...

最大连续数列的和  Description 求最大连续子序列的和 Input 第一行输入n(n<=500),第二行为n个以空格分开的整数(-1000到1000之间)； Output 该序列中最大的连续子序列的和 Sample Input 6 1 2 -5 6 7 8  Sample Output 21  解题思路 这道题其实就是从从前往后加，如果现在的数加上前面的数小于0，就将这个数赋值为0，最后再在这个数列里找出最大值。 状态转移方程:  i f ( a [ i ] + f [ i − 1 ] < 0 ) f [ i ] = 0 ; e l s e f [ i ] = a [ i...

完全背包（二维数组）  Description 设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。 Input 第一行：两个整数，M(背包容量，M<= 200)和N(物品数量，N<= 30)； 第2…N+1 行：每行二个整数Wi,Ui，表示每个物品的重量和价值。 Output 仅一行，一个数，表示最大总价值。 Sample Input 12 4 2 1 3 3 4 5 7 9  Sample Output 15  解题思路 这道题的思...

合唱队形  Description N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。   合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<…Ti+1>…>TK(1<=i<=K)。   你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 Input 输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=...

合并石子  Description 在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请设计一个程序，计算出将N堆石子合并成一堆的最小得分。 Input 每组数据第1行为一个正整数N(2<=N<=100)，以下N行，每行一个正整数，小于10000，分别表示第i堆石子的个数(1<=i<=N)。 Output 对于每组数据输出一个正整数，即最小得分 Sample Input 7 13 7 8 16 21 4 18  Sample Output 239  解题思路 这道题有三种方法...