最长上升子序列（LIS）题目合集

有关最长上升子序列的详细算法解释在http://www.cnblogs.com/denghaiquan/p/6679952.html

1）51nod 1134

　　一题裸的最长上升子序列，由于N<=50000，n算法会超时，只能用nlogn算法。

　

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 //#define LOCAL

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const int maxn = +;

 const LL mod = +;

 int a[maxn];

 int dp[maxn];

 int Binary_search(int key, int len)

 {

     int l=, r=len+;

     while(l<r)

     {

         int middle = (l+r) >> ;

         if(key>=dp[middle])

             l = middle +;

         else

             r = middle;

     }

     return l;

 }

 int main()

 {

     #ifdef LOCAL

         freopen("input.txt" , "r", stdin);

     #endif // LOCAL

         int n, len;

         scanf("%d", &n);

         for(int i=;i<n;i++)    scanf("%d", &a[i]);

         dp[] = a[];

         len = ;

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

         {

             if(a[i] > dp[len])

                 dp[++len] = a[i];

             else{

                 int j = Binary_search(a[i], len);

                 dp[j] = a[i];

             }

         }

         printf("%d\n", len);

     return ;

 }

2）POJ 2533

　　裸的最长上升子序列，N<=1000， n算法可以过。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 //#define LOCAL

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const int maxn = +;

 const LL mod = +;

 int a[maxn];

 int dp[maxn];

 int main()

 {

     #ifdef LOCAL

         freopen("input.txt" , "r", stdin);

     #endif // LOCAL

     int n;

     scanf("%d", &n);

     for(int i=;i<n;i++)    scanf("%d", &a[i]);

     dp[]=;

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

     {

         dp[i] = ;

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

         {

             if(a[j]<a[i] && dp[j]+ > dp[i])

                 dp[i] = dp[j] + ;

         }

     }

     int ans = ;

     for(int i=;i<n;i++)    ans = max(ans, dp[i]);

     printf("%d\n", ans);

     return ;

 }

3）POJ 1631

　　一题裸的最长上升子序列，由于N<=50000，n算法会超时，只能用nlogn算法。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 //#define LOCAL

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const int maxn = +;

 const LL mod = +;

 int a[maxn];

 int dp[maxn];

 int Binary_search(int key, int len)

 {

     int l=, r=len+;

     while(l<r)

     {

         int middle = (l+r) >> ;

         if(key>=dp[middle])

             l = middle +;

         else

             r = middle;

     }

     return l;

 }

 int main()

 {

     #ifdef LOCAL

         freopen("input.txt" , "r", stdin);

     #endif // LOCAL

     int T;

     scanf("%d", &T);

     while(T--)

     {

         ms(dp, );

         ms(a, );

         int n, len;

         scanf("%d", &n);

         for(int i=;i<n;i++)    scanf("%d", &a[i]);

         dp[] = a[];

         len = ;

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

         {

             if(a[i] > dp[len])

                 dp[++len] = a[i];

             else{

                 int j = Binary_search(a[i], len);

                 dp[j] = a[i];

             }

         }

         printf("%d\n", len);

     }

     return ;

 }

4）POJ 1887

　　这题是找最长下不上升子序列。发现n算法可以过。不过要注意输出。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 //#define LOCAL

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const int maxn = +;

 const LL mod = +;

 int a[maxn];

 int dp[maxn];

 int main()

 {

     #ifdef LOCAL

         freopen("input.txt" , "r", stdin);

     #endif // LOCAL

     int t=;

     while(scanf("%d", &a[])&&a[]!=-)

     {

         if(t>) printf("\n");

         int n =, ans =  ;

         while(scanf("%d", &a[n])&&a[n]!=-) n++;

         dp[]  = ;

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

         {

             dp[i] = ;

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

             {

                 if(a[j] > a[i] && dp[j]+ > dp[i])

                     dp[i] = dp[j] + ;

             }

         }

         for(int i=;i<n;i++)    ans = max(ans, dp[i]);

         printf("Test #%d:\n",t++);

         printf("  maximum possible interceptions: %d\n", ans);

         ms(a, );

         ms(dp, );

     }

     return ;

 }

5）POJ 1609

　　这题同样是最长不上升子序列，不过是2个关键词，先排序一个，再在另一个里面找最长不上升子序列。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 //#define LOCAL

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const int maxn = +;

 const LL mod = +;

 int a[maxn];

 int dp[maxn];

 struct node

 {

     int l, m;

 };

 bool cmp(node x1, node x2)

 {

     if(x1.l != x2.l)

         return x1.l > x2.l;

     return x1.m > x2.m;//当第一个关键字相同的时候，第2个关键字要从大到小排序

 }

 int main()

 {

     #ifdef LOCAL

         freopen("input.txt" , "r", stdin);

     #endif // LOCAL

     int n;

     while(scanf("%d", &n))

     {

         if(n == ) {printf("*\n");break;}

         node blocks[maxn];

         for(int i = ;i < n;i++)    scanf("%d%d", &blocks[i].l, &blocks[i].m);

         sort(blocks, blocks+n, cmp);

         dp[] = ;

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

         {

             dp[i] = ;

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

             {

                 if(blocks[j].m >= blocks[i].m && dp[j] +  > dp[i])

                     dp[i] = dp[j]+;

             }

         }

         int ans = ;

         for(int i=;i<n;i++)    ans = max(ans, dp[i]);

         printf("%d\n", ans);

         ms(dp, );

     }

     return ;

 }