首页 > 代码库 > POJ 1836 Alignment 最长递增子序列(LIS)的变形
POJ 1836 Alignment 最长递增子序列(LIS)的变形
大致题意：给出一队士兵的身高，一开始不是按身高排序的。要求最少的人出列，使原序列的士兵的身高先递增后递减。
求递增和递减不难想到递增子序列，要求最少的人出列，也就是原队列的人要最多。
1 2 3 4 5 4 3 2 1
这个序列从左至右看前半部分是递增，从右至左看前半部分也是递增。所以我们先把从左只右和从右至左的LIS分别求出来。
如果结果是这样的：
A[i]={1.86 1.86 1.30621 2 1.4 1 1.97 2.2} //原队列
a[i]={1 1 1 2 2 1 3 4}
b[i]={3 3 2 3 2 1 1 1}
如果是A[1]~A[i]递增，A[i+1]~A[8]递减。此时就是求：a[1]~a[i]之间的一个值与b[i+1]~b[8]之间的一个值的和的最大值。
O(n^2)和O(nlogn)算法都可以过。
O(n^2)算法：
#include <iostream>#include <cstdio>using namespace std;const int Max=1e3+5;int main(){ //freopen("in.txt","r",stdin); int n; scanf("%d",&n); double a[Max]={0}; for(int i=0; i<n; i++) scanf("%f",a+i); int l[Max]= {0},r[Max]= {0}; l[0]=r[n-1]=1; for(int i = 1; i < n; i++) { int maxLen = 0; for(int j = 0; j < i; j++) if(a[j]<a[i]) maxLen = max(maxLen,l[j]); l[i] = maxLen + 1; } for(int i=n-2; i>=0; i--) { int maxLen=0; for(int j=n-1; j>i; j--) if(a[j]<a[i]) maxLen=max(maxLen,r[j]); r[i]=maxLen+1; } int maxlen=0; for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) maxlen=max(maxlen,l[i]+r[j]); printf("%d\n",n-maxlen); return 0;}
O(nlogn)算法
#include <iostream>#include <cstdio>using namespace std;const int Max=1e3+5;int l[Max]= {0},r[Max]= {0};double B[Max];int BinarySearch(double *a, double value, int n){ int low = 0; int high = n - 1; while(low <= high) { int mid = (high + low) / 2; if(a[mid] == value) return mid; else if(value<a[mid]) high = mid - 1; else low = mid + 1; } return low;}int LIS_DP_NlogN(double *a, int n,int *Len){ int nLISLen = 1; B[0] = a[0]; for(int i = 1; i < n; i++) { if(a[i] > B[nLISLen - 1]) { B[nLISLen] = a[i]; nLISLen++; Len[i]=nLISLen; } else { int pos = BinarySearch(B, a[i], nLISLen); B[pos] = a[i]; Len[i]=pos+1; } } return nLISLen;}int main(){ //freopen("in.txt","r",stdin); int n; scanf("%d",&n); double a[Max]={0}; double b[Max]={0}; l[0]=r[0]=1; for(int i=0; i<n; i++) { scanf("%f",a+i); b[n-i-1]=a[i]; } LIS_DP_NlogN(a,n,l); LIS_DP_NlogN(b,n,r); int maxlen=0; for(int i=0;i<n-1;i++) for(int j=n-i-2;j>=0;j--) maxlen=max(maxlen,l[i]+r[j]); printf("%d\n",n-maxlen); return 0;}
POJ 1836 Alignment 最长递增子序列(LIS)的变形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。