POJ 1836 Alignment 最长递增子序列(LIS)的变形
2018-06-17 23:37:33来源:未知 阅读 ()
大致题意:给出一队士兵的身高,一开始不是按身高排序的。要求最少的人出列,使原序列的士兵的身高先递增后递减。
求递增和递减不难想到递增子序列,要求最少的人出列,也就是原队列的人要最多。
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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- poj-1753题题解思路 2020-01-26
- POJ1852 2019-11-11
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash