一、选择题
1、Rod-cutting Problem: Given a rod of total length N inches and a table of selling prices PL for lengths L=1,2,⋯,M. You are asked to find the maximum revenue RN obtainable by cutting up the rod and selling the pieces. For example, based on the following table of prices, if we are to sell an 8-inch rod, the optimal solution is to cut it into two pieces of lengths 2 and 6, which produces revenue R8=P2+P6=5+17=22. And if we are to sell a 3-inch rod, the best way is not to cut it at all.
| Length L | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Price PL | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 23 | 28 |
Which one of the following statements is FALSE?
A.This problem can be solved by dynamic programming
B.The time complexity of this algorithm is
C.If N≤M, we have
D.If N>M, we have
解析：D。题中说的是对于现有确定长度的杆子的分段出售问题，自然是可以用动态规划算法来处理，A正确。而对于我们该如何切分杆子，我们自然是需要对于其每一种长度进行遍历，因此我们可以给出这样的表格：
| 1 | 2 | ... | N | |
|---|---|---|---|---|
| 1 | 5 | 5+5 | ... | 5+...+5 |
| 2 | 5 | 5+5 | ... | |
| ... | 5 | 5+5 | ... | |
| N | 5 | 5+5 | ... |
表格中第一行表示我们现有的杆子的总长度L，而第一列表示我们在要求最大长度不大于M的情况下的最优分配方式。我们把总长度为L，要求最大长度不大于M的最优分配方式记作（L，M），存放在第M行的第L个格子中（计算格子不包括坐标轴）。那么，我们可以发现，如果我们现在有了（L-1，M）、（L，M-1）、（L-M，M）这三者时，我们可以通过(L,M)=
