HDU 1257 最少拦截系统 ——（LIS）

　　想了一下感觉和lis有关，交了果然AC。想不到很好的证明方法，试做证明如下：lis的每一个点都是一个不上升系统中的一员，设其为a[i],那么a[i-1]=a[i]，那么它肯定属于a[i]这个系统，如果它小于a[i]，且：1.大于a[i-1]的话，违背了lis的性质，2.<=a[i-1]的话，x属于a[i-1]这个系统。不可能有别的情况了。

　　归纳如下：给定一个序列，它的LIS长度就是它非上升子序列的个数。

　　代码如下：

 1 #include 
 2 #include 
 3 #include <string.h>
 4 using namespace std;
 5 const int inf = 0x3f3f3f3f;
 6 const int N = 30000 + 5;
 7 
 8 int a[N];
 9 int dp[N];
10 
11 int main()
12 {
13     int n;
14     while(scanf("%d",&n) == 1)
15     {
16         for(int i=1;i<=n;i++) scanf("%d",a+i);
17         memset(dp,inf,sizeof dp);
18         for(int i=1;i<=n;i++)
19         {
20             *lower_bound(dp+1,dp+1+n,a[i]) = a[i];
21         }
22         printf("%d\n",lower_bound(dp+1,dp+1+n,inf) - (dp+1));
23     }
24     return 0;
25 }

转载于:https://www.cnblogs.com/zzyDS/p/6400127.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！