首页 > 代码库 > POJ1836:Alignment(LIS的应用)
POJ1836:Alignment(LIS的应用)
题目链接：http://poj.org/problem?id=1836
题目要求：
给你n个数，判断最少去掉多少个数，从中间往左是递减的序列，往右是递增的序列需注意的是中间可能为两个相同的值,如 1 2 3 3 2 1 输出为0题目分析：
这题和UVA10534极其相似，因为刚做完，就果断粘贴复制了，唯一的不同是如果中间有两个士兵一样高是不用去掉的，（中间，仅限两个）。
我感觉这题是水过去的，我的代码只支持有一个最大值的情况，我的做法是先判断，如果求得最大值时这个点在队列当中的位置如果在边界，则直接结束。
否则，当在最大值时看之后有没有和最大值相同的值。~~~~怎么说呢，就是水过去的。
代码：
#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#include <math.h>#define eps 1e-9using namespace std;int n,ad[10002],ad2[10002],sum,len,l2;double a[10002],d[10002],w[10002];int er(double q[],int l,int r,double key)//好好研究二分{ int mid; while(l<=r) { mid=(l+r)/2; if(q[mid]==key) { return mid; } else if(q[mid]>key) { r=mid-1; } else l=mid+1; } return l;}int main(){ int we; while(scanf("%d",&n)!=EOF) { for(int i=1; i<=n; i++) { scanf("%lf",&a[i]); } sum=1; len=1; d[len]=a[1]; ad[1]=1; for(int i=2; i<=n; i++) { if(a[i]>d[len]) { d[++len]=a[i]; ad[i]=len; } else { we=er(d,1,len,a[i]); d[we]=a[i]; ad[i]=we; } } l2=1; w[l2]=a[n]; ad2[n]=1; for(int i=n-1; i>=1; i--) { if(a[i]>w[l2]) { w[++l2]=a[i]; ad2[i]=l2; } else { we=er(w,1,l2,a[i]); w[we]=a[i]; ad2[i]=we; } } int key=1; for(int i=1;i<=n;i++) { if(sum<(ad[i]+ad2[i]-1)) { sum=ad[i]+ad2[i]-1; key=i; } } if(ad[key]==1||ad2[key]==1) { printf("%d\n",n-sum); continue; } int F=0; if(ad[key]==ad2[key]) { for(int i=n;i>key;i--) { if(a[i]==a[key]) { F=1; printf("%d\n",n-sum-1); break; } } } if(F==1) continue; if(a[key-1]==a[key]||a[key]==a[key+1]) { printf("%d\n",n-sum-1); } else printf("%d\n",n-sum); } return 0;}
POJ1836:Alignment(LIS的应用)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。