动态规划一、背包问题1、0/1背包[问题背景及描述]Bessie 正在减肥，所以她规定每天不能吃超过C (10 <= C <= 35,000)卡路里的食物。

农民John 在戏弄她，在她面前放了B (1 <= B <= 21) 捅食物。

每桶内都有某个单位卡路里(范围：1..35,000)的食物(不一定相同)。

Bessie 没有自控能力，一旦她开始吃一个桶中的食物，她就一定把这桶食物全部吃完。

Bessie 对于组合数学不大在行。

请确定一个最优组合，使得可以得到最多的卡路里，并且总量不超过C。

例如，总量上限是40卡路里，6 桶食物分别含有7, 13, 17, 19, 29, 和31卡路里的食物。

Bessie可以吃7 + 31 = 38卡路里，但是可以获取得更多：7 + 13 + 19 = 39卡路里。

没有更好的组合了。

[输入]共两行。

第一行，两个用空格分开的整数：C 和 B第二行，B个用空格分开的整数，分别表示每桶中食物所含的卡路里。

[输出]共一行，一个整数，表示Bessie能获得的最大卡路里，使她不违反减肥的规则。

[输入样例]40 67 13 17 19 29 31[样例输出]392、固定次数的0/1背包有N种物品和一个容量为V的背包。

第i种物品最多有n[i]件可用，每件体积是c[i]，价值是w[i]。

求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

V〈30000，n〈100，n[i]〈50。

输入输出格式：第1行，两个用空格分开的整数：v 和n第2—n+1行，每件体积是c[i]，价值是w[i],最多有n[i]件可用[输入样例]40 210 20 520 30 6[样例输出]803、重复背包货币系统money母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。

[In their ownrebellious way],，他们对货币的数值感到好奇。

传统地，一个货币系统是由1,5,10,20 或25,50, 和100的单位面值组成的。

母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。

举例来说, 使用一个货币系统{1,2,5,10,...}产生18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。

写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。

保证总数将会适合long long (C/C++) 和Int64 (Free Pascal)。

输入格式：money.in货币系统中货币的种类数目是V 。

(1<= V<=25)要构造的数量钱是N 。

(1<= N<=10,000)第1 行：二整数，V 和N第2 ..V+1行：可用的货币V 个整数(每行一个每行没有其它的数)。

输入格式：money.out单独的一行包含那个可能的构造的方案数。

[输入样例]3 101 2 5输出：104、多个限定条件的背包NASA(美国航空航天局)因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋,因此在各方压力下终止了航天飞机的历史,但是此类事情会不会在以后发生，谁也无法保证,在遇到这类航天问题时,解决方法也许只能让航天员出仓维修,但是多次的维修会消耗航天员大量的能量,因此NASA便想设计一种食品方案,让体积和承重有限的条件下多装载一些高卡路里的食物.描述Description航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.输入格式Input Format第一行两个数体积最大值(<400)和质量最大值(<400)第二行一个数食品总数N(<50).第三行－第3+N行每行三个数体积(<400) 质量(<400) 所含卡路里(<500)输出格式Output Format一个数所能达到的最大卡路里(int范围内)样例输入Sample Input320 3504160 40 12080 110 240220 70 31040 400 220样例输出Sample Output550二、最长上升或下降序列1、拦截导弹某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例输入：389 207 155 300 299 170 158 656{最多能拦截的导弹数}2{要拦截所有导弹最少要配备的系统数}2、某农场有一个由按编号次序排列的n根木桩构成的首尾不相连的围栏。

现要在这个围栏中选取一些木桩，按照原有的编号次序排列之后，这些木桩的高度成为一个升序序列。

所谓的升序序列就是序列中的任何一个数都不小于它之前的任何一个数。

试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数t最大，并求出选出t根木桩的方案总数c。

例如：围栏由高度分别为10，1，9，8，7，6，3，4，6的木桩构成，则选出的高度为1，3，4，6的木桩是满足题意的选取方案。

输入格式：文件中的第1行只有一个数m，表明随后有m个问题的描述信息。

每个问题的描述信息格式为n h1 h2 h3，，，hn输出格式：依次输出每个问题中t和c的解。

每行输出一个问题的解。

例如输入：39 10 1 9 8 7 6 3 4 63 100 70 1026 40 37 23 89 91 12输出：4 12 2333、合唱队形(chorus.pas／dpr／c／cpp)【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K 位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入文件】输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。

第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【样例输入】8186 186 150 200 160 130 197 220【样例输出】4【数据规模】对于50％的数据，保证有n<=20；对于全部的数据，保证有n<=100。

三、数列的连续最大和1、数列的连续最大和，顾名思义，就是在一个长度为n的数列{An}中，求i，j （1<=i<=j<=n），使得数列{An}中，第i个元素到第j个元素之间，所有元素的和最大。

分析：以第i个数结尾的最大连续和序列，可能存在两种选择：情形一：只包含Ai情形二：包含Ai和以Ai-1结尾的最大连续和序列设F(i)表示以第i个数结尾的最大连续和转移方程：F(i)=max{Ai , F(i-1)+Ai}边界：F(1)=A1要求的结果为max{F(i)|1<=i<=n}仔细思考题目后，符合动态规划条件。

用ans[i]表示包含数列第i项的前i个元素的最大和，数组no存放数列元素，则状态转移方程为：ans[0]=0；ans[i]=max{ans[i-1]+no[i],no[i]} 时间复杂度为O(n)核心程序代码：best:=-maxlongint;temp:=0;for i:=1 to n dobegininc(temp,no[i]);if temp>best then best:=temp;if temp<0 then temp:=0;end;2、最大子序和问题描述输入一个长度为ｎ的整数序列（A1,A2,……,An），从中找出一段连续的长度不超过M 的子序列，使得这个序列的和最大。

例如：序列1，-3，5，1，-2， 3当M=2或3时S=5+1=6当M=4时S=5+1+(-2)+3=7数据范围:50%的数据N,M<=1000100%的数据N,M<=20000初步分析 枚举设F(i)为以Ai 结尾长度不超过M 的最大子序和对于每个F(i)，从1到m 枚举k 的值，完成Aj 的累加和取最大值。

该算法的时间复杂度为O(n2)简化方程3、holiday.pas/c/cppDescription经过几个月辛勤的工作，FJ 决定让奶牛放假。

假期可以在1…N 天内任意选择一段（需要连续），每一天都有一个享受指数W 。

但是奶牛的要求非常苛刻，假期不能短于P 天，否则奶牛不能得到足够的休息；假期也不能超过Q 天，否则奶牛会玩的腻烦。

FJ 想知道奶牛们能获得的最大享受指数。

Input(holiday.in)第一行：N,P,Q.第二行：N 个数字，中间用一个空格隔开。

Output(holiday.out)一个整数，奶牛们能获得的最大享受指数。

Sample Input5 2 4-9 -4 -3 8 -6Sample Output5Limitationtime:1s ∑+-===i k i j jm k A i F 1}..1|max{)(∑==i 1j j A )i (S 令∑+-===i k i j j m k A i F 1}..1|max{)(}..1|)(min{)(}..1|)()(max{m k k i S i S m k k i S i S =--==--=memory:65536kb50% 1≤N≤10000100% 1≤N≤100000Hint选择第3-4天，享受指数为-3+8=5。

守望者的逃离(escape.pas/c/cpp)【问题描述】恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。

守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。

为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。

到那时，岛上的所有人都会遇难。

守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。

庆幸的是守望者拥有闪烁法术，可在1s 内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。