小木棍问题，要求用数据结构与算法处理

Question

有一堆数量为n的木棍。他们的长度和重量是已知的。这些棍子将以一个接一个的形式被一台木工机床处理。木工机床为处理一根木棍所需要的准备时间称为装配时间。装配时间与机器复位和转换工具及外形有关。装备时间服从以下几条规律：
（a）处理第一根木棒的装配时间是1分钟
（b）正确地处理好一根长度为l重量为w的木棍后，如果机器处理的下一根木棒的长度l'和重量w'符合l<=l'和w<=w'那么处理下一根木棒将不需要装配时间。否则将需要1分钟的装配时间。
你的任务是找出处理一堆木棍所需的最小装配时间。例如，如果你有5根木棍，长度和重量分别为(4,9), (5,2), (2,1), (3,5), 和 (1,4)。那么最小的装配时间将是2分钟，当以这种顺序装配时:(1,4), (3,5), (4,9), (2,1), (5,2)。
要求：
（1）输入：本题一共有T组数据。第一行有一个整数T,代表数据组数。每一组数据由两行组成：第一行包含一个整数n,1<=n<=5000,代表木棍的数量；第二行包含2*n个正整数l1, w1, l2, w2, ..., ln, wn,每个数都不超过10000,代表每根木棍的长度和重量。每两个数之间可能有一个或多个空格。
（2）输出：输出每组数据的最小装配时间。
（3）所设计的数据结构应尽可能节省存储空间。
（4）程序的运行时间应尽可能少。

Answer 1

如果只是要输出最小装配时间的话，不需要什么数据结构
其实算法很简单：记f(n)为装配n个木棍需要的最小装配时间
w[p], l[p]存储需要装配时间的序列中的最后一个木棍的weight、length（p=0 to n）
有f(1) = 1 (w[0], l[0])即第一根木棍的参数
f(2) = 1(存在一个木棍的weight和length都小于另一个) (w[0], l[0])为质量/长度大的那个
f(2) = 2(不存在) (w[0], l[0]), (w[1], l[1])
f(n) = f(n - 1) (存在i(0<=i<f(n)),使得第n根木棍的长度和质量同时大于或小于(w[i],l[i])
若大于,则(w[i], l[i]) = 第n根木棍的长度和质量
f(n) = f(n - 1) + 1 (不存在上述情况，且此时(w[f(n)], l[f(n)])=第n根木棍的长度和质量)
此算法可以看成是递推吧
代码如下
#include <iostream>
using namespace std;

int getAns(int number, int *weight, int *length)
{
int answer = 1;
int i, j;
int *w = new int [number], *l = new int [number];
bool add_one_min = true;

w[0] = weight[0], l[0] = length[0];

for (i = 1; i < number; i++)
{
add_one_min = true;
for (j = 0; j < answer && add_one_min; j++)
{
if (w[j] > weight[i] && l[j] > length[i])
add_one_min = false;

if (w[j] <= weight[i] && l[j] <= weight[j])
{
w[j] = weight[i];
l[j] = weight[j];
add_one_min = false;
}
}

if (add_one_min)
{
w[answer] = weight[i];
l[answer] = length[i];
answer++;
}
}

delete []w;
delete []l;
return answer;
}

int main()
{
int number, weight[5000], length[5000];
int i;

cin >> number;
for (i = 0; i < number; i++)
cin >> weight[i] >> length[i];

cout << getAns(number, weight, length);
return 0;
}