3

私はLIS2spoj http://www.spoj.com/problems/LIS2/misofで問題を解決し NICEDAYていました。この投稿によると: http://apps.topcoder.com/forums/;jsessionid=F39EBDDC41BEB792536BE044ADC8BA2A?module=Thread&threadID=615154&start=0&mc=2 . これら2つの質問の間のリンクを理解することも、misofのソリューションの複雑さを理解することもできませんNICEDAY.

PS:ソリューション全体は必要ありません。また、この問題には複雑すぎるため、2D セグメント ツリーを介したアプローチも必要ありません (私は試しました)。

4

2 に答える 2

1

私には、この問題に 2D セグメント ツリーを使用できないと思います。なぜなら、2D セグメント ツリーには最大で 10^5 x 10^5 のテーブルが必要になるため、大きすぎるからです。

于 2013-08-03T20:43:48.237 に答える
1

1 次元の問題をどのように解決するかを考えてみましょう。

dp[i] = longest increasing subsequence that ends at position i.

ごとに、最大であるようなものiに追加a[i]する必要があります。配列の定義を変更することにより、高度なデータ構造を使用してこれを効率的に見つけることができます。jdp[j]a[j] < a[i]dp

dp[i] = longest increasing subsequence that ends with the VALUE i

さて、最初dp[ a[i] ] = 1はそれぞれの位置についてi. 次に、各要素a[i]について、最大の が必要ですdp[0], dp[1], ..., dp[ a[i] - 1 ]。次に、あなたが持っていdp[ a[i] ] = mx + 1ます。

You can find this maximum by normalizing your array values (make sure they are all in the interval [1, n]). You can do this with a sort. For example, if your array is 42 562 13, the n = 3 and your new array will be 2 3 1.

This can be implemented easily with a segment tree that supports queries and updates for maximums. The time complexity will be O(n log n).

This can be extended quite easily to your problem by using 2D segment trees, obtaining time complexity O(n log^2 n), which should not be too complex at all. This involves using a segment tree whose nodes are also segment trees.

于 2013-06-29T10:17:08.450 に答える