一、Help Jimmy
场景中包括多个长度和高度不同的平台，地面是最低的平台，高度为0，长度无限。
一个老鼠叫“Jimmy”，它在时刻0从高于所有平台的某处开始下落，下落速度始终是1米/秒。当Jimmy落到某个平台上时，游戏者选择它向左还是向右跑，跑动速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过Max米，不然就会摔死，游戏结束。
设计一个程序，计算Jimmy到地面时可能的最早时间。
解题思路：
Jimmy跳到一块板上后，可以有两种选择：向左或向右。走到左端和走到右端所需要的时间易算。如果我们能知道，以左端为起点到达地面的最短时间，和以右端为起点到达地面所需要的时间，就易选择从右端还是左端出发。整个问题就可以分解成两个子问题，即Jimmy所在位置下方第一块板左端为起点到达地面的最短时间，和右端为起点到达地面所需要的最短时间。这两个子问题在形式上和原问题上时完全一致的。将板子从上到下从1开始进行无重复的编号（越高的板子编号越小，高度相同的板子编号在前在后无所谓），那么和上面两个子问题相关的变量就只有板子的编号。
不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子，假设LeftMinTime(k)表示从k号板子左端到达地面的最短时间，RightMinTmie(k)表示从k号半只右端到达地面的最短时间，方法如下：
if(板子k左端正下方没有板子)
{
? if(板子k的高度h(k)大于Max)? LeftMinTime(k)=∞;
? else? LeftMinTime(k)=h(k);
}?
else if(板子k左端正下方的板子编号是m)
{
? LeftMinTime(k)=h(k)-h(m)+Min(LeftMinTime(m)+Lx(k)-Lx(m),RightMinTime(m)+Rx(m)-Lx(k));
}
上面，h(i)代表i号板子的高度，Lx(i)代表i号板子左端点的横坐标，Rx(i)代表i号板子右端点的横坐标。那么h(k)-h(m)就是从k号板子跳到m号板子所需要的时间，Lx(k)-Lx(m)就是从m号板子的落脚点走到m号板子左端点的时间，Rx(m)-Lx(k)就是从m号板子的落脚点走到右端所需要的时间。
求RightMinTime(k)过程类似。不妨认为Jimmy开始的位置是一个编号为0，长度为0的板子，那么整个问题就是求LeftMinTime(0)。
的呼入数据中，板子并没有按照高度排序，做之前需要将板子排序。
二、滑雪
滑雪时为了获得速度，滑的区域必须向下倾斜。
输入：
输入的第一行代表区域的行数R和列数C，(1<=R,C<=100)。下面是R行，每行有C个整数，高度为h，0<=h<=10000。
输出：输出最长区域的长度
样例输入：
5? 5?
1? ? 2? ? 3? ? 4? ? 5
16? 17? 18? 19? 6
15? 24? 25? 20? 7
14? 23? 22? 21? 8
13? 12? 11? 10? 9
样例输出：25
解题思路：
L(i,j)表示从点(i,j)出发的最长滑行长度。一个点(i,j)，如果周围没有比它低的点，L(i,j)=1。否则，递推公式：L(i,j)等于L(i,j)周围四个点中比(i,j)低，且L值最大的那个点的L值，再加1。复杂度：O(n2)
（从小到大递推） 将所有点按高度从小到大排序，每个点的L值都初始化为1，从小到大遍历所有的点。经过一个点(i.j)时，用递推公式求L(i,j)。
三、神奇的口袋
输入：输入第一行时正整数n(1<=n<=20)，表示不同的物品的数目。接下来的n行，每一行有一个1到40之间的正整数，分别给出a1,a2,a3....an的值。
输出：输出不同的选择物品的方式的数目。
输入样例：3? 20? 20? 20
输出样例：3
#include <iostream>
using namespace std;
int a[30];
int N;
int Ways[50][30];
int main()
{
cin>>N;
memset(Ways,0,sizeof(Ways));
for(int i=1;i<=N;++i)
{
cin>>a[i];
Ways[0][i]=1;
}
Ways[0][0]=1;
for(int w=1;w<=40;++w)
{
for(int k=1;k<=N;++k)
{
Ways[w][k]=Ways[w][k-1];
if(w-a[k]>=0) Ways[w][k]+=Ways{w-a[k]][k-1];
}
}
cout<<Ways[40][N];
return 0;
}四、分蛋糕
问题描述：
有一块矩形大蛋糕，宽和高分别是整数w、h。现要将其切成m块小蛋糕，每个小蛋糕都必须是矩形、且宽和高均为整数。切蛋糕时，每次切一块蛋糕，将其分成两个矩形蛋糕。
请计算：最后得到的m块小蛋糕中，最大的那块蛋糕的面积下限。
假设w=4 h=4 m=4，则下面的切法可使其中最大蛋糕块的面积最小。
假设w=4 h=4 m=3，则下面的切法可使其中最大蛋糕块的面积最小。
输入：共有多行，每行表示一个测试案例。每行是三个用空格分开的整数W，H，M，其中1<=W? H,M<=20，M<=WH。当W=H=M=0时不需要处理，表示输入结束。
输出：每个案例的测试结果占一行，输出一个整数，表示最大蛋糕块的面积下限。
样例输入：
4? ?4? ?4? ?
4? ?4? ?3
0? ?0? ?0
样例输出：
4
6
解题思路：
设ways(w,h,m)表示宽为w，高为h的蛋糕，被切m刀后，最大的那块蛋糕的面积的最小值
题目要求就是ways(W,H,M-1)
边界条件：w*h<m+1 INF
? ? ? ? ? ? ? ? ? m==0? ? ? ?w*h
递推式：
? SV为第一刀竖着切时能得到的最好结果，SH为第一刀横着切时能得到的最好结果，则ways(w,h,m)=min(SV,SH)
? SV=min{Si,i=1,2.....w-1}其中:Si=为第一刀左宽为i的情况下的最好结果
? Si=min{max(ways(i,h,k),ways(w-1,h,m-1-k)),k=0,1,2...m-1}