解题报告：hdu1257 LIS裸题

2017-09-02 17:28:44

writer：pprp

那个裸题练练手，讲解在之前的博客中提到了

代码如下：

/*

@theme:hdu1257

@writer:pprp

@begin:17:13

@end:17:26

@declare:LIS的裸题,温习一下

@error:注意题目中说明了是多组数据

@date:2017/9/2

*/

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

int arr[maxn];

int dp[maxn];

int main()

{

    //freopen("in.txt","r",stdin);

    int N,Max = ;

    while(cin >> N)

    {

        Max = ;

        for(int i =  ; i < N; i++)

        {

            dp[i] = ;

            cin >> arr[i];

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

            {

                if(arr[j] < arr[i])

                {

                    dp[i] = max(dp[j]+,dp[i]);

                }

            }

            Max = max(Max,dp[i]);

        }

        cout << Max << endl;

    }

    return ;

}

第二种不用dp的解法：

代码如下：

/*

@theme:hdu1257

@writer:pprp

@begin:17:13

@end:17:36

@declare:LIS的裸题,温习一下

@error:

@date:2017/9/2

*/

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

int arr[maxn];

int tmp[maxn];

int main()

{

    //freopen("in.txt","r",stdin);

    int N,len = ;

    while(cin >> N)

    {

        len = ;

        cin >> arr[];

        tmp[len] = arr[];

        for(int i =  ; i < N ; i++)

        {

            cin >> arr[i];

            if(arr[i] > tmp[len])

            {

                len++;

                tmp[len] = arr[i];

            }

            else

                *lower_bound(tmp,tmp+len,arr[i]) = arr[i];

        }

        cout << len << endl;

    }

    return ;

}