Q1.城市交通路网
【算法分析】
我们将每对友好城市看成一条线段，则这道题的描述化为：有N条线段，问最少去掉多少条线，可以使剩下的线段互不交叉？
第一，以北岸为线的起点而南岸为线的终点；先将所有的线按照起点坐标值从小到大排序，按照每条线的终点坐标计算交叉数：求线I的交叉数A[I]，则检查所有1..I-1条线，若线J( 1<= J< I)的终点值大于线I的终点值，则线I与线J相交。A[I]与A[J]同时加1。整个搜索量最大为5000*5000。
第二，将A数组从大到小排序，每删除一条线，则将与之相交的线的A值减1，重复这个过程，直到所有A值都为0。此时剩下的线则全不交叉。
如上数据，则可得下面结果：
| 编号 | 南岸 | 北岸 | 交叉数 |
| 1 | 1 | 3 | 2 |
| 2 | 2 | 4 | 2 |
| 3 | 3 | 1 | 2 |
| 4 | 4 | 5 | 1 |
| 5 | 5 | 2 | 3 |
此时，1、2、3航线的交叉数都一样，如果删去的是3、5线，则剩下的1、2、4线互不相交，最多航线数为3；但如果删去的是2、3，则还要删去第5线才符合要求，此时的最多航线数为2，不是最优解。
于是，我们从上面的分析中再深入，将航线按起点坐标排好序后，如上所述，在本题中，只要线J的起点小于线I的起点，同时它的终点也小于线I的终点，则线J和线I不相交。因此，求所有线中最多能有多少条线不相交，实际上是从终点坐标值数列中求一个最长不下降序列。这就把题目转化为一个非常典型的动态规划题目了。
求最长不下降序列的规划方程如下：
L(Si)=max{L(Sj)}+1；1< = j < i且 Sj < Si。Si为航线的终点坐标值。
从以上分析过程可以得出：当我们拿到一道题时，不要急于求解，而应先将题目的表面现象一层层象剥竹笋一样去掉，只留下最实质的内容。这时再来设计算法，往往能事半功倍。
Q2.合唱队形
【算法分析】
我们按照由左而右和由右而左的顺序，将n个同学的身高排成数列。如何分别在这两个数列中寻求递增的、未必连续的最长子序列，就成为问题的关键。设
a 为身高序列，其中a[i]为同学i的身高；
b 为由左而右身高递增的人数序列，其中 b[i]为同学1‥同学i间（包括同学i）身高满足递增顺序的最多人数。显然b[i]=max{b[j]|同学j的身高<同学i的身高}+1；
c为由右而左身高递增的人数序列，其中c[i]为同学n‥同学i间（包括同学i）身高满足递增顺序的最多人数。显然c[i]=max{c[j]|同学j的身高<同学i的身高}+1；
由上述状态转移方程可知，计算合唱队形的问题具备了最优子结构性质(要使b[i]和c[i]最大，子问题的解b[j]和c[k]必须最大(1≤j≤i-1 ，i+1≤k≤n))和重迭子问题的性质(为求得b[i]和c[i]，必须一一查阅子问题的解b[1]‥b[i-1]和c[i+1]‥c[n])，因此可采用动态程序设计的方法求解。
显然，合唱队的人数为max{b[i]+c[i]}-1(公式中同学i被重复计算，因此减1)，n减去合唱队人数即为解。
这个算法的时间复杂度为O(n2)，在1秒时限内可解决n≤100范围内的问题。
Q3.最长公共子序列
提示:
最长公共子串（Longest Common Substring）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。字符串长度小于等于1000。
分析：
与最长不下降子序列(LIS)类似的，我们可以以子序列的结尾作为状态，但现在有两个子序列，那么直接以两个子序列当前的结尾作为状态即可。
①确定状态： 设F[x][y]表示S[1..x]与T[1..y]的最长公共子序列的长度。答案为F[|S|][|T|]。
②确定状态转移方程和边界条件：
分三种情况来考虑：
·S[x]不在公共子序列中：该情况下F[x][y]=F[x-1][y]；
·T[y]不在公共子序列中：该情况下F[x][y]=F[x][y-1]；
·S[x]=T[y]，S[x]与T[y]在公共子序列中：该情况下，F[x][y]=F[x-1][y-1]+1。
F[x][y]取上述三种情况的最大值。综上：
状态转移方程：F[x][y]=max{F[x-1][y],F[x][y-1],F[x-1][y-1]+1},其中第三种情况要满足S[x]=T[y]； 边界条件：F[0][y]=0,F[x][0]=0。
③程序实现：
计算F[x][y]时用到 F[x-1][y-1],F[x-1][y],F[x][y-1]这些状态，它们要么在F[x][y]的上一行，要么在F[x][y]的左边。因此预处理出第0行，然后按照行从小到大、同一行按照列从小到大的顺序来计算就可以用迭代法计算出来。时间复杂度为O(|S|*|T|)。
Q4.机器分配
【算法分析】
按照公司的顺序来分配机器，即按照公司的顺序划分阶段，
第一个阶段把M台设备分给第一个公司，记录下来获得的各个盈利值，
然后把M台设备分给前两个公司，和第一个阶段比较记录下来更优的各个盈利值，
一直到第N个阶段把M台机器全部分给了N个公司，就可以得到最优解，
下面来讨论两个阶段之间的关系，设数组F[I][J]表示前I个公司分配J台机器的最大盈利，数组F[I-1][K]表示前I-1个公司分配K台机器的最大盈利(1≤I≤N,1≤J≤M,0≤K≤J),用Value[I][J]表示第I个公司分配 J台机器的盈利, 则F[I][J]可以由下面的式子中取最大值获得：
F[I-1][0]+Value[I][J] //前I-1公司分配0台机器最大盈利+第I个公司分配J台的机器的盈利
F[I-1][1]+Value[I][J-1] //前I-1公司分配1台机器最大盈利+第I个公司分配J-1台的机器的盈利
F[I-1][2]+Value[I][J-2] //前I-1公司分配2台机器最大盈利+第I个公司分配J-2台的机器的盈利
F[I-1][J-1]+Value[I][1] //前I-1公司J-1分配台机器最大盈利+第I个公司分配1台的机器的盈利
F[I-1][J]+Value[I][0] //前I-1公司分配J台机器最大盈利+第I个公司分配0台的机器的盈利
在这里用机器数用做每个阶段的状态，由于Value[I][J]的值为定值，要使前面每个式子的值最大，就必须使第i-1阶段的各个状态的值最大，阶段i的状态只能由阶段i-1中的状态通过状态转移方程求得，与其他状态没有关系。由此可见，该问题具备了最优子结构和无后效性原则，适宜使用动态程序设计方法求解。
状态转移方程为：F[I][J]=MAX{F[I-1][K]+Value[I][J-K]} (1≤I≤N,1≤J≤M,0≤K≤J)
初始值：F[0][0]=0，F[n][m]的值即为所求最大盈利值。
