poj 2533:最長上昇サブシーケンス

最近またpoj试験を准备して、この问题を见て、アルゴリズムの设计と分析の授业の上で言ったことがあることを覚えていて、しかしずっと最も良い方法を思い出せなくて、长い间やって、最后にデータの规模を见て马鹿な方法Aを使いました.
 

 : 2000ms  : 65536kB

 

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).



Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

 

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

 

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

 

7

1 7 3 5 9 4 8

 

4

 

Northeastern Europe 2002, Far-Eastern Subregion

最良の方法は次のとおりです.
コアコンセプトは、1つのインクリメンタルシーケンスを維持することであり、1つのデータにアクセスするたびに、このインクリメンタルシーケンスを通じて、現在自分より小さいデータで構成できる上昇シーケンスが最も長いかどうかを調べることができる.具体的な方法:最初はチェーンテーブルを増やして空にし、最初から配列を巡り、最初の数字をチェーンテーブルに追加してからアクセスを続け、アクセスした数字が現在のチェーンテーブルの末尾の数字よりも大きい場合はチェーンテーブルに追加し、アクセスした数字が現在のチェーンテーブルの末尾の数字より小さい場合は、チェーンテーブルを逆方向にクエリーします.アクセスした数値よりも小さい最初の数値が見つかるまで、アクセスした数値はチェーンテーブルでクエリーした数値の次の数値に置き換えられます.完全な配列を巡回すると、チェーンテーブルの長さは、その配列の最長上昇サブシーケンスの長さとなります.時間複雑度はO(nk),kはチェーンテーブルの長さである.
もちろんチェーンテーブルではなく配列でこのインクリメンタルシーケンスを維持する具体的な方法を見ましたが、この配列はインクリメンタルなので、検索するたびに二分検索で行うことができます.そうすると時間の複雑さはO(nlogk)で、興味があればこのブログを見ることができます.中にはよく紹介されていますが、例もあります.

 
私の弱いBコードは下で贴って、みんなは见て良い0 0

#include <iostream>

using namespace std;

int a[1001]={0};

int len[1001]={0};

int main()

{

    int n;

    while(cin>>n){

        len[0] = 1;

        for(int i = 0; i < n; i ++){

            cin>>a[i];

            int m = 0;

            for(int j = 0; j < i; j ++)

            {

                if(m < len[j] && a[j] < a[i]){

                    m = len[j];

                }

                    

            }

            len[i] = m+1;

        }

        int m = 0;

        for(int i = 0; i < n; i ++)

        {

            if(m < len[i])

                m = len[i];

        }

        cout<<m<<endl;

    }

    return 0;

}