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 
     
      using namespace std;const int maxn = 1010;int arr[maxn];int dp[maxn];int main(){    //freopen("in.txt","r",stdin);    int N,Max = 0;    while(cin >> N)    {        Max = 0;        for(int i = 0 ; i < N; i++)        {            dp[i] = 1;            cin >> arr[i];            for(int j = 0 ; j < i ; j++)            {                if(arr[j] < arr[i])                {                    dp[i] = max(dp[j]+1,dp[i]);                }            }            Max = max(Max,dp[i]);        }        cout << Max << endl;    }    return 0;}
     

 

第二种不用dp的解法：

代码如下：

/*@theme:hdu1257@writer:pprp@begin:17:13@end:17:36@declare:LIS的裸题,温习一下@error:@date:2017/9/2*/#include 
     
      using namespace std;const int maxn = 1010;int arr[maxn];int tmp[maxn];int main(){    //freopen("in.txt","r",stdin);    int N,len = 0;    while(cin >> N)    {        len = 1;        cin >> arr[0];        tmp[len] = arr[0];        for(int i = 1 ; 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 0;}