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 の後です。

num[i] < bestrun[j+1]3)内側のループの状態をチェックする必要がありますか? 条件的には満足できると思いますnum[i] > bestrun[j]。

役立つ回答をお待ちしています。
ご協力いただきありがとうございます！

4

1 に答える 1

2

1)bestrun[i]は、長さ i + 1 の最長減少サブシーケンスの開始である最小整数を追跡します。したがって、現在の より小さい値に遭遇した場合は、その値bestrun[0]に変更する必要があります。bestrun[0]長さ 1 の最小の減少サブシーケンス。

2) あなたが何を求めているのかよくわかりません。シーケンスを反転するとどうなるか疑問に思っている場合は、代わりに最長増加サブシーケンス アルゴリズムを実行して同じ結果を得ることができます。

3) はい、それは冗長であるように思われますbestrun。実際、最長増加/減少サブシーケンスの一部の実装では、この事実を利用して、バイナリ検索を実行してよりも大きい最高jのものを見つけることにより、実行時間を O(n log n) に改善しています。num[i]bestrun[j]

于 2012-11-13T03:07:54.920 に答える