2

我对 USACO Training 的 TEXT Dynamic Programming 部分中关于经典问题（查找最大递减子序列）的代码感到困惑。这是文章链接。请帮我搞定！

这是代码：

 1  #include <stdio.h>
 2  #define MAXN 200000
 3  main () {
 4      FILE *in, *out;
 5      long num[MAXN], bestrun[MAXN];
 6      long n, i, j, highestrun = 0;
 7      in = fopen ("input.txt", "r");
 8      out = fopen ("output.txt", "w");
 9      fscanf(in, "%ld", &n);
10      for (i = 0; i < n; i++) fscanf(in, "%ld", &num[i]);
11      bestrun[0] = num[n-1];
12      highestrun = 1;
13      for (i = n-1-1; i >= 0; i--) {
14          if (num[i] < bestrun[0]) {
15            bestrun[0] = num[i];
16            continue;
17        }
18        for (j = highestrun - 1; j >= 0; j--) {
19            if (num[i] > bestrun[j]) {
20                if (j == highestrun - 1 || num[i] < bestrun[j+1]){
21                    bestrun[++j] = num[i];
22                    if (j == highestrun) highestrun++;
23                    break;
24                }
25            }
26        }
27      }
28      printf("best is %d\n", highestrun);
29      exit(0);
30  }

我有3个问题：

1) 第 14-17 行到底是做什么的？例如对于序列 10, 2, 8, 9, 4, 6, 3 ，该代码的结果是 4 但它的子序列是 10, 8, 4, 2 是错误的，因为原始序列中的元素 2 是在 8 和 4 之前，但在结果子序列中是在 8 和 4 之后！

2）考虑序列5,10,8,9,4,6,3。根据上面的代码，最大递减子序列的长度是4，这个子序列是10,5,4,3。但是在这个子序列中相反原始序列 5 在 10 之后。

3）是否有必要检查num[i] < bestrun[j+1]内循环中的条件？我认为它以前满足num[i] > bestrun[j]条件。

我在等你有用的答案。
谢谢你的帮助！

4

1 回答 1

2

1)bestrun[i]跟踪长度为 i + 1 的最长递减子序列的开始的最小整数。因此，如果遇到小于当前的值，则bestrun[0]需要更改bestrun[0]为该值，因为那将是长度为 1 的最小递减子序列。

2）我不太确定你在问什么。如果您想知道翻转序列时会发生什么，那么您可以运行最长递增子序列算法来获得相同的结果。

3）是的，这似乎是多余的，bestrun应该是不增加的。事实上，最长递增/递减子序列的一些实现利用这一事实通过进行二分搜索以j找到num[i]大于bestrun[j].

于 2012-11-13T03:07:54.920 回答