温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
动态规划（一） &
NOIP2000T2
NOIP2007P3
NOIP2008P3
NOIP2007T3
NOIP2008T3
NOIP2006T1
NOIP2000T4
NOIP2002P4
VIJOSP1322
NOIP2006P2
NOIP2006T2
VIJOSP1306
NOIP1999T4
VIJOSP1299
VIJOSP1285
VIJOSP1283
VIJOSP1246
VIJOSP1243
VIJOSP1242
VIJOSP1235
NOIP2003P2
VIJOSP1198
VIJOSP1194
VIJOSP1180
VIJOSP1175
VIJOSP1159
VIJOSP1157
VIJOSP1153
VIJOSP1144
VIJOSP1143
VIJOSP1139
NOIP2001P4
NOIP2001T3
NOIP2001T2
VIJOSP1111
NOIP2005P3
NOIP2003T3
NOIP2004T3
VIJOSP1073
VIJOSP1071
VIJOSP1069
VIJOSP1063
VIJOSP1061
VIJOSP1059
VIJOSP1057
VIJOSP1038
VIJOSP1037
VIJOSP1025
VIJOSP1014
VIJOSP1011
VIJOSP1006
NOIP2005T2
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 1.乘积最大 【题目描述】 &&&&今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
&&& 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 &&& 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： &&& 有一个数字串：312， 当N=3，K=1时会有以下两种分法： &&& 1） 3*12=36 &&& 2） 31*2=62 &&& 这时，符合题目要求的结果是：31*2=62 &&& 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 【输入格式】 程序的输入共有两行： 第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为N的数字串。 【输出格式】 结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 【输入样例】 4 2 1231 【输出样例】 62 【解题指导】 &&&&设f[i,j]为前i个数字中插入j个乘号的最大值
&&& 转移方程： &&& f[i,j]=max{f[p-1,j-1]*num(p,i)}其中2≤p≤i,num(p,i)为从p开始到i的数字组成的整数值。
&&& 因为最终的结果可能会很大，必须采用高精度。以下的参考程序没有考虑高精度。 【测试数据】 &&&&&&&& & 2．守望者的逃离 【题目描述】 &&&&恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。
&&& 现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意：守望者跑步、闪烁或休息活动均以秒(s)为单位，且每次活动的持续时间为整数秒。距离的单位为米(m)。 【输入格式】 输入文件仅一行，包括空格隔开的三个非负整数M, S, T。 【限制】 30%的数据满足：1 &= T &= 10, 1 &= S &= 100 50%的数据满足：1 &= T &= 1000, 1 &= S &= 10000 100%的数据满足：1 &= T &=
&= M &= 1000, 1 &= S &= 108. 【输出格式】 输出文件包含两行： 第1行为字符串“Yes”或“No”（区分大小写），即守望者是否能逃离荒岛。 第2行包含一个整数。第一行为“Yes”（区分大小写）时表示守望者逃离荒岛的最短时间；第一行为“No”（区分大小写）时表示守望者能走的最远距离。 【输入样例】 样例1： 39 200 4
样例2： 36 255 10 【输出样例】 样例1： No 197
样例2： Yes 6 & 3．传球游戏 【题目描述】 &&&&上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
&&& 游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。
&&& 聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1-&2-&3-&1和1-&3-&2-&1，共2种。 【输入格式】 输入文件共一行，有两个用空格隔开的整数n，m（3&=n&=30，1&=m&=30）。 【输出格式】 输出文件共一行，有一个整数，表示符合题意的方法数。 【输入样例】 3 3 【输出样例】 2 & 4．矩阵取数游戏 【题目描述】 &&&&帅帅经常更同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij据为非负整数。游戏规则如下：
&&& 1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素； &&& 2. 每次取走的各个元素只能是该元素所在行的行首或行尾； &&& 3. 每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）； &&& 4. 游戏结束总得分为m次取数得分之和。 &&& 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。 &&& 【输入格式】 输入文件game.in包括n+1行； 第一行为两个用空格隔开的整数n和m。 第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开 【输出格式】 输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大的分。 【输入样例】 样例1： 2 3 1 2 4 3 4 2
样例2： 1 4 【输出样例】 样例1： 82
样例2： 122
【输入输出样例1解释】 第1次：第一行取行首元素，第二行取行尾元素，本次的氛围1*21+2*21=6 第2次：两行均取行首元素，本次得分为2*22+3*22=20 第3次：得分为3*23+4*23=56。总得分为6+20+56=82 & 5．传纸条 【题目描述】 &&&&小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。
&&& 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。
&&& 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。
&&& (massage.pas/c/cpp) 【输入格式】 输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1≤m,n≤50）。 接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。 【限制】 30%的数据满足：1≤m,n≤10 100%的数据满足：1≤m,n≤50 【输出格式】 输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。 【输入样例】 3 3 0 3 9 2 8 5 5 7 0 【输出样例】 34 【解题指导】 &&&&动态规划，考虑一张纸条的情形然后推广到两张纸条，传一张纸条然后传回完全等价于从起点直接传两张纸条到终点，于是满足动态规划。 & 6．字串距离 【题目描述】 &&&&设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcb□cd”、“□a□bcbcd”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。
&&& 如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为他们的ASCII码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为0。在字符串A，B的所有扩展串中，必定存在两个等长的扩展串A1，B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A，B的距离。
&&& 请你编写一个程序，求出字符串A，B的距离。 【输入格式】 输入文件第一行为字符串A，第二行为字符串B。A、B均有小写字母组成且长度均不超过2000。第三行为一个整数K（1≤K≤100），表示空格与其他字符的距离。 【输出格式】 输出文件仅包含一个整数，表示所求的字符串A、B的距离。 【输入样例】 cmc snmn 2 【输出样例】 10 & 7． 数字三角形 【题目描述】 &&&&如下所示三角形：
&&& 7 &&& 3 8 &&& 8 1 0 &&& 2 7 4 4 &&& 4 5 2 6 5 &&& 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。 &&& 规则如下： &&& 1.每一步可沿直线向下或右斜线向下走； &&& 2.1&=三角形行数&=200； &&& 3.三角形中的数字为整数0,1,...,99。 【输入格式】 第一行为一个自然数，表示数字三角形的行数n，接下来的n行表示一个数字三角形。 【输出格式】 仅有一个数，即要求的最大总和。 【输入样例】 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 【输出样例】 30 【测试数据】 &&&& & 8．BUY LOW，BUY LOWER 【题目描述】 &&&&“低价购买”这条建议是在奶牛股票市场取得成功的一条规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议：“低价购买；再低价购买”。每次你购买一支股票，你必须用低于你上次购买它的价格购买它。买的次数越多越好！你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将会得到一段时间内一支股票每天的出售价（2e16范围内的正整数），你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价买进；再低价购买”的原则。写一程序计算最大购买次数。 【输入格式】 第一行：N（1&=N&=5000），股票发行天数。 第二行：N个数，是每天的股票价格。 【输出格式】 输出文件仅包含两个数：最大购买次数和拥有最大购买次数的方案数（小于等于2e31）当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候），这2种方案被认为是相同的。 【输入样例】 12 68 69 54 64 68 64 70 67 78 62 98 87 【输出样例】 4 2 【测试数据】 &&&&&& & 9．能量项链 【题目描述】 &&&&在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。
&&& 需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
&&& 例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号&表示两颗珠子的聚合操作，(j&k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
&&& (4&1)=10*2*3=60。 &&& 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 &&& ((4&1)&2)&3）=10*2*3+10*3*5+10*5*10=710。 【输入格式】 输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。 【输出格式】 输出文件energy.out只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。 【输入样例】 4 2 3 5 10 【输出样例】 710 & 10．花瓶插花 【题目描述】 &&&&你想以最美观的方式布置花店的橱窗。你有F束花，每束花的品种都不一样，同时至少有同样数量的花瓶。它们被按顺序排成一排，花瓶的位置是固定的，并从左到右，从1 到 V编号，编号为V 的花瓶在最右边。花束可以移动，并且每束花用1到F的整数唯一标识。标识花束的整数决定了花束在花瓶中的排列的顺序，如果i&j，则花束i必须放在花束j左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中。秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶只能放一束花。
&&& 每一个花瓶的形状和颜色也不同，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空花瓶的美学值为0。在上述例子中，花瓶与花束不同的搭配所具有的美学值，可以用如下的表格表示：
1 (杜鹃花)
2 (秋海棠)
3 (康乃馨)
&&& 根据表格，杜鹃花放在花瓶2中，会显得非常好看，但若放你在花瓶4中则显得很难看。为了取得最佳美学效果，必须保持花束顺序的条件下，使花的摆放取得最大美学值，如果具有最大美学值的摆放不止一种，则输出任意一种。 【输入格式】 第一行包含两个数： F, V。（1&=F&=100， F&=V&=100 ） 接下来的F行：包含V个数，输入Aij矩阵。 (-50&=Aij&=50，Aij为第i束花放在第j个花瓶中的美学值) 【输出格式】 第一行输出最大美学值 第二行给出方案 【输入样例】 3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20 【输出样例】 53 2 4 5 【解题指导】 &&&& 类似0/1背包问题。 &&& a[i,j]=花i放入瓶j的美学价值 &&& s[i,j]=前i束花放入前j个花瓶内的最大美学价值 &&& 决策：花i放不放在第j个瓶中。 &&& (1)放：s[i,j]=s[i-1,j-1]+a[i,j] &&& (2)不放：s[i,j]=s[i,j-1] &&& 取s[i,j]=max{s[i-1,j-1]+a[i,j],s[i,j-1]} & 11．字串编辑距离 【题目描述】 &&&&设A和B是两个字符串。我们用最少的字符操作，将字符串A转换为字符串B。这里所说的字符操作包括：
&&& (1)删除一个字符； &&& (2)插入一个字符； &&& (3)将一个字符改为另一个字符。 &&& 将字符串A转换为字符串B所用的最少字符操作数称为字符串A到字符串B的编辑距离，记为s(A，B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离s(A，B)。
&&& 【输入格式】 共两行，第一行表示字符串A，第二行表示字符串B。(字符长度均小于100) 【输出格式】 只有一行，为A，B的编辑距离。 【输入样例】 ab abc 【输出样例】 1 【解题指导】 &&&&s(i,j)=将A的前i个字符变成B的前j个字符的最少操作数。
&&& 如果A[i]=B[j] &&& 求s(i,j)考虑在以下三种操作中取最小值： &&& (1)删除一个字符；s(i-1,j) &&& (2)插入一个字符；s(i,j-1) &&& (3)将一个字符改为另一个字符；s(i-1,j-1) &&& 如果A[i]&&B[j] &&& 求s(i,j)考虑在以下三种操作中取最小值： &&& (1)删除一个字符；s(i-1,j) &&& (2)插入一个字符；s(i,j-1) &&& (3)将一个字符改为另一个字符；s(i-1,j-1)+1 &&& & 12．方格取数 【题目描述】 &&&&设有N*N的方格图(N&=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示：
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
&&& 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。 【输入格式】 输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。 【输出格式】 只需输出一个整数，表示2条路径上取得的最大的和。 【输入样例】 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 【输出样例】 67 【解题指导】 &&&&要使前一条路不影响到后面一条，于是只能一起走，状态可以用4维数组来保存。
&&& 设F[x1,y1,x2,y2]表示第一条走到x1，y1，第二条走到x2，y2时的最大值； &&& &&& 状态转移方程： &&& F[x1,y1,x2,y2]:=max{F[x1-1,y1,x2-1,y2],F[x1-1,y1,x2,y2-1],F[x1,y1-1,x2-1,y2],F[x1,y1-1,x2,y2-1]}+a[x1,y1]+
&&& a[x2,y2](在不出界的情况下） & 13．马拦过河卒 【题目描述】 &&&&棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
&&& 　　棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 【输入格式】 一行四个数据，分别表示B点坐标和马的坐标。 【输出格式】 一个数据，表示所有的路径条数。 【输入样例】 6 6 3 3 【输出样例】 6 & 14．解题 【题目描述】 &&&&过去的日子里,农夫John的牛没有任何题目. 可是现在他们有题目,有很多的题目。 &&& 精确地说,他们有P (1 &= P &= 300) 道题目要做。他们还离开了农场并且象普通人一样找到了工作. 他们的月薪是M (1 &= M &= 1000) 元。 &&& 他们的题目是一流的难题,所以他们得找帮手.帮手们不是免费的,但是他们能保证在一个月内作出任何题目.每做一道题需要两笔付款, 第一笔A_I(1 &= A_I &= M)元在做题的那一个月初支付, 第二笔B_I元(1 &= B_I &= M)在做完后的下一个月初支付. 每一个月牛们用上一个月挣的钱来付款. 牛没有任何存款意识, 所以每个月的节余都回拿用去买糖吃掉了。 &&& 因为题目是相互关连的,它们必须按顺序解出. 比如,题目3必须在解题目4之前或同一个月解出。 &&& 找出牛们做完所有题目并支付完所有款项的最短月数。 【输入格式】 第一行: M 和 P; 【输出格式】 第一行: 牛们做完题目和付完帐目的最少月数. 【输入样例】 100 5 40 20 60 20 30 50 30 50 40 40 【输出样例】 6 & 15．开心的金明 【题目描述】 &&&&金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数1~5 表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v[j]，重要度为w[j]，共选中了k 件物品，编号依次为j1…jk，则所求的总和为：v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单. 【输入格式】 输入的第1 行，为两个正整数，用一个空格隔开： N m （其中N（&30000）表示总钱数，m(&25)为希望购买物品的个数。）
从第2 行到第m+1 行，第j 行给出了编号为j-1 的物品的基本数据，每行有2 个非负整数 v p （其中v 表示该物品的价格（v≤10000），p 表示该物品的重要度（1~5）） 【输出格式】 输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的 最大值（&） 【输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【输出样例】 3900 【解题指导】 &&&&典型的0/1背包问题，把总钱数N元当作背包容量，物品价格当作重量，重要度和价格的乘积当成参考价值，就可直接套用背包问题动态规划程序求解。
16．金明的预算方案 【题目描述】 &&&&金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
&&& 主件 附件 &&& 电脑 打印机，扫描仪 &&& 书柜 图书 &&& 书桌 台灯，文具 &&& 工作椅 无 &&& 如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
&&& 设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。 【输入格式】 输入文件的第1行，为两个正整数，用一个空格隔开： N m 其中N（&32000）表示总钱数，m（&60）为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数 v p q （其中v表示该物品的价格（v&10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q&0，表示该物品为附件，q是所属主件的编号） 【输出格式】 输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值 （&200000）。 【输入样例】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【输出样例】 2200 【解题指导】 &&&&“每个主件可以有０个，１个或２个附件”。也就是说对于一套物品（包含主件，所有的附件），我们称为一个属类，对一个属类的物品的购买方法，有以下５种：
&&& 　　　　１.一个都不买 &&& 　　　　２.主件 &&& 　　　　３.主件＋附件１ &&& 　　　　４.主件＋附件２ &&& 　　　　５.主件＋附件１＋附件２ &&& 这五种购买方法也是唯一的五种方法，也就是说对一属类的物品，我们只有上述的５种购买方法。　于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品的属类作为dp的状态。可以得到如下的dp方程：
&&& 　 f[i,j]=max{f[i-1,j]; &&& 　　 f[i-1,j-v[i,0]]+v[i,0]*w[i,0]; &&& 　 　 f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]; &&& 　　 f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2]; &&& 　　 f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];}
&&& 需要注意的是必须对输入数据进行重新处理，使之按属类重新编号。 &&& 最后注意题目中还有一个条件：“每件物品都是10元的整数倍”，也就是说我们先可以把价格都除以10，总钱数也除以10，这样就可以少循环10倍，不过最后的结果记得要乘上10。 17．递增序列 【题目描述】 &&&& 给定一个数字串，请你插入若干个逗号，使得该数字串成为一个严格递增的数列且分成的数的个数最多，在这个问题中，前导的零是允许出现在数的前面的。 【输入格式】 一行,是一个长度不超过80的数字串 【输出格式】 按次序输出严格递增且分成的数的个数最多，相邻两个数之间用一个逗号隔开，如果有多个数列满足要求，则输出第一个数最大的那个数列，若这样的解还不止一个，则输出第二个数最大的那个数列，以此类推。 【输入样例】
【输出样例】 1,2,5,12,3123 & 18．导弹拦截 【题目描述】 &&&&某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试验阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 【输入格式】 输入数据只有一行，该行包含若干个数据，之间用半角逗号隔开，表示导弹依次飞来的高度（导弹最多有 20 枚，其高度为不大于 30000 的正整数）。 【输出格式】 输出数据只有一行，该行包含两个数据，之间用半角逗号隔开。第一个数据表示这套系统最多能拦截的导弹数；第二个数据表示若要拦截所有导弹至少要再添加多少套这样的系统。 【输入样例】 389,207,155,300,299,170,158,65 【输出样例】 6,1 【解题指导】 &&&&最多能拦截的导弹数就是求输入序列的最长不升序列长度，总共需要的拦截系统是输入序列的最长上升序列长度，所求即为这个长度减一。
&&& 这里要注意的是对输入的处理问题，因为输入序列是用逗号隔开的，不能直接READ，只能作为字符读入后再进行处理，这里有两个可行的办法，一种是一个一个字符读入，遇到逗号就开始存数，另一种是一次性读入整个字符串，再利用pos,copy,delete等字符串处理函数把数字提取出来。 & 19．古城之谜 【题目描述】 &&&&著名的考古学家石教授在云梦高原上发现了一处古代城市遗址。让教授欣喜的是在这个他称为冰峰城(Ice-Peak City)的城市中有12块巨大石碑，上面刻着用某种文字书写的资料，他称这种文字为冰峰文。然而当教授试图再次找到冰峰城时，却屡屡无功而返。
&&& 幸好当时教授把石碑上的文字都拍摄了下来，为了解开冰峰城的秘密，教授和他的助手牛博士开始研究冰峰文，发现冰峰文只有陈述句这一种句型和名词(n)、动词(v)、辅词(a)这三类单词，且其文法很简单：
&&& &文章& 　　::= &句子& { &句子& } &&& &句子& 　　::= &陈述句& &&& &陈述句&　　::= &名词短语& { &动词短语& &名词短语& } [ &动词短语& ] &&& &名词短语& ::= &名词& | [ &辅词& ] &名词短语& &&& &动词短语& ::= &动词& | [ &辅词& ] &动词短语& &&& &单词&　　 ::= &名词& | &动词& | &辅词& &&& 注：其中&名词&、&动词&和&辅词&由词典给出，“::=”表示定义为，“|”表示或，{}内的项可以重复任意多次或不出现，[]内的项可以出现一次或不出现。
&&& 在研究了大量资料后，他们总结了一部冰峰文词典，由于冰峰文恰好有26个字母，为了研究方便，用字母a到z表示它们。 &&& 冰峰文在句子和句子之间以及单词和单词之间没有任何分隔符，因此划分单词和句子令石教授和牛博士感到非常麻烦，于是他们想到了使用计算机来帮助解决这个问题。假设你接受了这份工作，你的第一个任务是写一个程序，将一篇冰峰文文章划分为最少的句子，在这个前提下，将文章划分为最少的单词。 【输入格式】 输入文件第1行为词典中的单词数n（n&=1000）。 输入文件第2行至第(n+1)行每行表示一个单词，形为“α.mot”， α表示词性，可能是n(名词),v（动词）,a（辅词）中的一个，mot为单词，单词的长度不超过20。拼写相同而词性不同的单词视为不同的单词，如输入示例中的n.kick与v.kick是两个不同的单词。
输入文件第(n+2)行为需要划分的文章，以“.”结束。 输入文件中的文章确保为冰峰文。文章是由有限个句子组成的，每个句子只包含有限个单词。文章长度不超过5KB。 【输出格式】 输出文件为两行，每行一个整数。 输出文件第1行为划分出来的句子数。 输出文件第2行为划分出来的单词数。 【输入样例】 11 n.table n.baleine a.silly n.snoopy n.sillysnoopy v.is v.isnot n.kick v.kick a.big v.cry sillysnoopyisnotbigtablebaleinekicksnoopysillycry 【输出样例】 2 9 & 20．佳佳的魔法药水 【题目描述】 &&& 发完了k张照片，佳佳却得到了一个坏消息：他的MM得病了！佳佳和大家一样焦急万分！治好MM的病只有一种办法，那就是传说中的0号药水……怎么样才能得到0号药水呢？你要知道佳佳的家境也不是很好，成本得足够低才行……得到一种药水有两种方法：可以按照魔法书上的指导自己配置，也可以到魔法商店里去买——那里对于每种药水都有供应，虽然有可能价格很贵。在魔法书上有很多这样的记载：1份A药水混合1份B药水就可以得到1份C药水。（至于为什么1+1=1，因为……这是魔法世界）好了，现在你知道了需要得到某种药水，还知道所有可能涉及到的药水的价格以及魔法书上所有的配置方法，现在要问的就是：1.最少花多少钱可以配制成功这种珍贵的药水；2.共有多少种不同的花费最少的方案（两种可行的配置方案如果有任何一个步骤不同则视为不同的）。假定初始时你手中并没有任何可以用的药水。 【输入格式】 第一行有一个整数N(N&=1000)，表示一共涉及到的药水总数。药水从0~N-1顺序编号，0号药水就是最终要配制的药水。
第二行有N个整数，分别表示从0~N-1顺序编号的所有药水在魔法商店的价格（都表示1份的价格）。 第三行开始，每行有3个整数A、B、C，表示1份A药水混合1份B药水就可以得到1份C药水。注意，某两种特定的药水搭配如果能配成新药水的话，那么结果是唯一的。也就是说不会出现某两行的A、B相同但C不同的情况。 【输出格式】 输出两个用空格隔开的整数，分别表示得到0号药水的最小花费以及花费最少的方案的个数。 【输入样例】 7 10 5 6 3 2 2 3 1 2 0 4 5 1 3 6 2 【输出样例】 10 3 & 21．佳佳的魔杖 【题目描述】 &&&&配制成功了珍贵的0号药水，MM的病治好了。轻松下来的佳佳意外的得到了一个好东西……那就是——一种非常珍贵的树枝。这些树枝可以用来做优质的魔杖！当然了，不能只做自己的，至少还要考虑到MM的对吧。选择怎样的切割方式来制作魔杖非常重要，关键问题是——一把魔杖既不能太长、又不能太短，且制作出来的魔杖不能有冲突……佳佳得到的这些树枝在属性上完全相同。每一个树枝都有n段（用1~n编号），给定了每段的长度L[I]和每段的魔力值M[I]。单独的一段是不可以从中间切开的，你可以做的就是选择一段或连续的几段，把它们作为一个整体切下来，再用来制作魔杖。但是一根魔杖的长度不能太长——不能大于给定的值hi；也不能太短——不能小于给定的值lo。
&&& 魔杖有一个奇怪的要求：如果某一根魔杖的制作材料是另一根魔杖的一部分，则这两根魔杖之间将发生冲突。比如说树枝有三段，从左到右的长度分别为4、 1、3，佳佳需要长度为4到5之间的魔杖。佳佳可以用一根树枝的前两段做出一个长度为5的魔杖，用一根树枝的后两段做出长度为4的魔杖；但他决不能用一根树枝的前两段做了魔杖后再单独使用另一根树枝的第一段做成魔杖，因为前者包含了后者的所有成分，这会导致冲突。
&&& 我们假设佳佳可以得到任意多这样的树枝。佳佳需要制作出若干个互不冲突的魔杖，使所有魔杖的魔力值之和最大。（魔杖的长度就是组成它的那些段的长度的总和，魔力值亦然）。 【输入格式】 第一行有三个用空格隔开的正整数，分别表示n、lo、hi。 第二行的n个用空格隔开的正整数就是L[1]、L[2]……L[n]。 第三行的n个用空格隔开的正整数就是M[1]、M[2]……M[n]。 输入文件以一个回车/换行符结尾。 【输出格式】 只用输出一个整数，表示能够获得的魔力值的最大值。 【输入样例】 6 4 5 1 3 3 2 2 1 2 3 1 4 5 2 【输出样例】 21 & 22．文科生的悲哀(二) 【题目描述】 &&&&化学不及格的Matrix67无奈选择了文科。他必须硬着头皮艰难地进行着文科的学习。这学期的政治、历史和地理课本各有n章。每一科的教学必须按章节从前往后依次进行。若干章政治、若干章历史和若干章的地理内容可以合成一个教学阶段。年级计划将整个学期的内容分成若干个阶段进行教学。为了保证各科教学进度相同，年级规定每一个阶段包含的各科的章节数必须相同。一个阶段包含的章节越多，这个阶段所需要的课时也就越多。经过研究，假如某个阶段包含政史地各k章，则政治学习需要花费3^k天的课时，历史学习需要花费5^k天的课时，地理学习需要花费2^k天的课时，最后还需要4天的综合训练。一个阶段所花费的总时间是以上四项时间的和。
&&& 为了便于安排时间，学校希望每个阶段恰好需要若干周来完成。因此，划分出的每一个阶段所需要的天数都必须是7的整数倍（高三是没有星期六和星期天的）。
&&& 那么，这学期的课程最多可以划分成多少个阶段呢？你会想到，要想划分的阶段数最多，一个阶段完成一章的任务就行了（因为3^1+5^1+2^1+4=14是7的整数倍）。但问题没有这么简单。每个课本都可能有一些独立性较强的连续章节，它们具有很强的连续性，必须在一个阶段中完成。如果你已知所有不能划分在两个或两个以上的阶段中的连续章节，你还能计算出最多能安排多少个阶段吗？ 【输入格式】 第一行有两个用空格隔开的正整数n和m，分别表示各科课本的章节数和不可分割的连续章节的个数。 　　第二行到第m+1行，每行告诉了一个信息，该信息说明了哪一个课本的第几章到第几章必须一次性完成。同一科目给定的章节有可能重复或有重叠。
　　每一行信息分为两个部分。第一部分是“Politics:”、“History:”、“Geography:”三个字符串中的一个；第二部分是用“-”连接的两个数字x,y(1&=x&Y&=N)，表示该行第一部分所示的课本从第X章到第Y章具有连续性。第二部分紧接在第一部分后面，没有任何符号分隔。
　　对于30%的数据，n,m&=10； 　　对于50%的数据，n,m&=1000； 　　对于100%的数据，n,m&=100 000。 【输出格式】 一个正整数，表示按照学校和年级的种种要求（见下）最多可以安排的阶段个数。 　　如果没有符合条件的安排方案，请输出-1。 　　注意：以下三个要求需要同时考虑。 　　　　1.每一个阶段包含的各科章数相同； 　　　　2.按时间函数计算出的各阶段所需天数必须是7的倍数； 　　　　3.给出的任一个连续章节都不能被分割开来。 【输入样例】 8 3 Politics:1-2 History:5-6 Politics:1-4 【输出样例】 3 & 23．生产产品 【题目描述】 &&&&在经过一段时间的经营后，dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架，而要开始自己生产产品了！产品的生产需要M个步骤，每一个步骤都可以在N台机器中的任何一台完成，但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同，它们完成每一个步骤的所需时间也不同。机器I完成第j个步骤的时间为T[I,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时，为了保证安全和产品的质量，每台机器最多只能连续完成产品的L个步骤。也就是说，如果有一台机器连续完成了产品的L个步骤，下一个步骤就必须换一台机器来完成。现在，dd_engi的OI商店有史以来的第一个产品就要开始生产了，那么最短需要多长时间呢？
&&& 某日Azuki.7对跃动说:这样的题目太简单,我们把题目的范围改一改 &&& 对于菜鸟跃动来说,这是个很困难的问题,他希望你能帮他解决这个问题 【输入格式】 第一行有四个整数M, N, K, L 下面的N行，每行有M个整数。第I+1行的第J个整数为T[I,J]。 【输出格式】 输出只有一行，表示需要的最短时间。 【输入样例】 3 2 0 2 2 2 3 1 3 1 【输出样例】 4 & 24．邮局问题 【题目描述】 &&& 一些村庄建在一条笔直的高速公路边上，我们用一条坐标轴来描述这条公路，每个村庄的坐标都是整数，没有两个村庄的坐标相同。两个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用与它距离最近的邮局，建立邮局的原则是：所有村庄到各自使用的邮局的距离总和最小。
&&& 数据规模：1&=村庄数&=300, 1&=邮局数&=30, 1&=村庄坐标&=10000 【输入格式】 2行
第一行:n m {表示有n个村庄，建立m个邮局} 第二行:a1 a2 a3 .. An {表示n个村庄的坐标} 【输出格式】 一行:l {l表示最小距离总和} 【输入样例】 10 5 1 2 3 6 7 9 11 22 44 50 【输出样例】 9 & 25．天堂的馈赠 【题目描述】 &&&& 小杉找到了做棉花糖的最优方案，想去摘云朵，可是摔死了…… &&& 他来到了天堂。 &&& 天堂当然是很大的，也是很缭乱的。 &&& 小杉看到一块路标，写着“天堂的馈赠”。 考虑到小杉刚死没多久，为了安抚他受创的心灵和思恋的感情， &&& 天堂派出一个天使给小杉送礼，但IQ不够高的小杉可不能够拿到好礼物。 &&& 馈赠在天堂门口进行。天使站在云端，往下扔礼物。 &&& 天堂之门的宽度为W格（按1..W编号），高度为0格，云端的高度为H格，小杉只能站在格子里。 &&& 开始时（第0秒），小杉站在天堂之门的第P格。 &&& 馈赠开始后，天使会在某些时刻从云端的某格扔礼物下来，礼物下落的速度（格/秒）是不一样的。 &&& 小杉左右移动去接礼物（每秒可以移动1格或不移动）。 &&& 礼物之间的价值当然是不一样的，小杉事先知道了每个礼物的价值。 &&& 当礼物在某一秒末恰好到达小杉所在的格子中，小杉就接到了这个礼物。 &&& 小杉想知道，他最多可以拿到价值为多少的礼物。 &&& 而且，由于礼物下落的速度有些可以很……，小杉还想知道是不是有些礼物他怎么样也拿不到。 【输入格式】 每组测试数据的 第一行有四个数W，P，H，N(1&=P&=W&=500)，(1&=H&=500)，(0&=N&=3000)
接下来N行，每行四个数t，r，v，s(0&=t&=1500)，(1&=r&=W)，(1&=v&=H)，(|s|&=1e5)
表示天使在t时刻，云端的第r格，以v格/秒的速度扔下价值s的礼物 输入均为正整数 10%的数据W&=100,H&=100,N&=200 【输出格式】 对每组测试数据输出两行。 第一行仅有一个整数，表示小杉最多能拿到价值多少的礼物。 第二行也仅有一个整数，表示小杉不可能拿到的礼物总价值多少。 【输入样例】 1 1 1 1 1 1 1 1 【输出样例】 1 0 & 26．数字游戏 【题目描述】 &&&&丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
&&& 例如，对于下面这圈数字（ n=4， m=2）： &&&
&&& 当要求最小值时， ((2-1) mod 10)& ((4+3) mod 10)=1& 7=7，要求最大值时，为 ((2+4+3) mod 10)& (-1 mod 10)=9& 9=81。特别值得注意的是，无论是负数还是正数，对 10取模的结果均为非负值。 &&& 丁丁请你编写程序帮他赢得这个游戏。 &&& 【输入格式】 输入文件第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有个整数，其绝对值不大于104，按顺序给出圈中的数字，首尾相接。 【输出格式】 输出文件有两行，各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。 【输入样例】 4 2 4 3 -1 2 【输出样例】 7 81 & 27．最佳课题选择 【题目描述】 &&&&Matrix67要在下个月交给老师n篇论文，论文的内容可以从m个课题中选择。由于课题数有限，Matrix67不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题I，若Matrix67计划一共写x篇论文，则完成该课题的论文总共需要花费Ai*x^Bi个单位时间（系数Ai和指数Bi均为正整数）。给定与每一个课题相对应的Ai和Bi的值，请帮助Matrix67计算出如何选择论文的课题使得他可以花费最少的时间完成这n篇论文。 【输入格式】 第一行有两个用空格隔开的正整数n和m，分别代表需要完成的论文数和可供选择的课题数。 　　以下m行每行有两个用空格隔开的正整数。其中，第I行的两个数分别代表与第I个课题相对应的时间系数Ai和指数Bi。 　　对于30%的数据，n&=10,m&=5； 　　对于100%的数据，n&=200，m&=20，Ai&=100，Bi&=5。 【输出格式】 输出完成n篇论文所需要耗费的最少时间。 【输入样例】 10 3 2 1 1 2 2 1 【输出样例】 19 & 28．多米诺骨牌 【题目描述】 &&&&有一个m 行n 列的矩形方格棋盘，1&=m,n&=10^9，用1*2 的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠，有多少种不同的覆盖的方法。JYY暗想，这题范围这么大，公式又那么难找，这怎么办呢？
&&& 于是他要求lhc做出让步，lhc不得不做出让步，现在1&=n&=10^9，1&=m&=5。于是JYY高兴地在5分钟内解决了这个问题，不幸的是他把这个程序弄丢了，但他从不把做过的东西再做一遍，于是他把任务交给了你。
&&& 请你帮助JYY编程解决:) &&& lhc不想看到长串的高精度数，你只需要求出覆盖方法总数 mod p 的值即可。 【输入格式】 一行，三个整数数n，m，p，1&=n&=10^9，1&=m&=5，1&=p&=10000。 【输出格式】 一个整数，总数 mod p 的结果。 【输入样例】 7 2 10 【输出样例】 1
阅读(1481)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'[转载]动态规划（一）',
blogAbstract:'
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}