文档介绍：动态规划
一、背包问题
1、0/1背包［问题背景及描述］
Bessie正在减肥，所以她规定每天不能吃超过C(10<=C<=35,000)卡路里的食物。农民John在戏弄她，在她面前放了B(1<=B<=21)捅食物。每桶内都有某个单位卡
38920715530029917015865
6｛最多能拦截的导弹数｝
2｛要拦截所有导弹最少要配备的系统数｝
2、某农场有一个由按编号次序排列的n根木桩构成的首尾不相连的围栏。现要在这个围栏中选取一些木桩，按照原有的编号次序排列之后，这些木桩的高度成为一个升序序列。所谓的升序序列就是序列中的任何一个数都不小于它之前的任何一个数。试编写程序从这个围栏中选取合适的木桩使得选出的木桩个数t最大，并求出选出t根木桩的方案总数C。例如：围栏由高度分别为10，1，9，8，7，6，3，4，6的木桩构成，则选出的高度为1，3，4，6的木桩是满足题意的选取方案。
输入格式：文件中的第1行只有一个数m，表明随后有m个问题的描述信息。每个问题的描述信息格式为nh1h2h3，，，hn
输出格式：依次输出每个问题中t和c的解。每行输出一个问题的解。
例如
输入：
3
91019876346
310070102
6403723899112
输出：
41
22
33
3、合唱队形
(／dpr／c／cpp)
【问题描述】
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2…，K,他们的身高分别为Tl,T2,…，TK,则他们的身高满足
Tl<...<Ti>Ti+l>…〉TK(1〈二i<=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
【输入文件】
(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
【输出文件】
，这一行只包含一个整数，就是最少需要几位同学出列。
【样例输入】
8
186186150200160130197220
【样例输出】
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;
fori:=1tondo
begin
inc(temp,no[i]);
iftemp>bestthenbest:=temp;
iftemp<0thentemp:=0;
end;
2、最大子序和
问题描述
输入一个长度为n的整数序列(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<=1000
100%的数据N,M<=20000
初步分析枚举
设
F(i)为以Ai结尾长度不超过M的最大子序和
F(i)=max{工1AIk=l..m}
j
j=i-k+1
对于每个F(i),从1到m枚举k的值，完成Aj的累加和取最大值。
该算法的时间复杂度为O(n2)
简化方程
令s(i)八iA
j
j=i
F(i)二max{JAIk二1・.m}
j
j=i-k+1
=max{S(i)一S(i-k)Ik=1・.m}
=S(i)—min{S(i—k)Ik=1・.m}
3、holiday・pas/c/cpp
Description
经过几个月辛勤的工作，