序
【问题背景】
zhx 给他的妹子们排序。
【问题描述】
zhx 有 N 个妹子，他对第 i 个妹子的好感度为a[i], 且所有a[i],两两不相等。现在 N 个妹子随意站成一排，他要将她们根据好感度从小到大排序。他使用的是冒泡排序算法（详见下）。
如果排序过程中好感度为a[i]的妹子和好感度为a[j]的妹子发生了交换，那么她们之间会发生一场口角。 现在 zhx 想知道，给定妹子的初始排列，在排序完成后，最多存在多少个妹子，她们任意两人之间没发生过口角。
正式地，考虑对数组a[i]进行冒泡排序，如果a[i]和a[j]在排序过程中发生交换，那么在两个元素之间连一条边。你需要求出，排序结束后，最多存在多少个元素，其中任意两个元素之间不存在连边。冒牌排序算法如下：
【输入格式】
第一行两个整数 N，表示妹子数量。
接下来一行 N 个整数a[i]，表示初始第 i 个妹子的好感度。
【输出格式】
一行一个整数，表示最多满足要求的妹子的个数。
【样例输入】
3
3 1 2
【样例输出】
2
【样例解释】
{1, 2}。
【数据规模与约定】
对于30%的数据，1 ≤ N ≤ 16。
对于70%的数据，1 ≤N ≤ 5000。
对于100%的数据，1 ≤ N ≤ 100000, 0 ≤ a[i] < N。
【题目分析】
最长上升子序列,因为我们要找的是一个最大的集合，在这个集合中所有的妹子都没有发生口角，那让这些妹子不发生口角的办法就是不交换，怎样做到不交换，如果初始状态已经是a[i]<a[j],就不需要交换，那就要找最长上升子序列。
//dp做法超时继续， #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=100010; int a[maxn],bh[maxn]; bool isno[maxn]={0}; int n,ans=0; int dp[maxn]; int LIS(int n) { int sum=1; for (int i=2;i<=n;i++) { int tmp=i; int maxx=0; for (int j=1;j<i;j++) { if (a[i]>a[j]) maxx=max(maxx,dp[j]); } dp[i]=maxx+1; if (dp[i]>sum) sum=dp[i]; } return sum; } int main() { freopen("sort.in","r",stdin); freopen("sort.ans","w",stdout); dp[1]=1; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int ans=LIS(n); if(ans==1) printf("0"); else printf("%d ",ans); return 0; }
//用二分nlogn #include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,ans=1; int Stack[100010],a[100010]; //Stack单调递增 int find(int x) { int l=1,r=ans; while(l<=r) { int mid=(l+r)>>1; if(x>Stack[mid]&&x<=Stack[mid+1]) return mid; else if(x>Stack[mid]) l=mid+1; else r=mid-1; } return 0; } int main() { freopen("sort.in","r",stdin); freopen("sort.ans","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); Stack[1]=a[1]; int t; for(int i=2;i<=n;i++) { if(a[i]>Stack[ans]) t=++ans; else t=find(a[i])+1;//因为search找到的是当前点的坐标，要想使T发挥它的最大价值，应该把他放在当前点的上一个点 Stack[t]=a[i]; } printf("%d",ans);//单调栈的长度即为LIS长度 fclose(stdin);fclose(stdout); return 0; }