poj1836

2019-11-10 18:26:54

字体：大中小

来源：转载

供稿：网友

题目大意：

给一组数字，求这组数字的最长下降子序列。

解题思路：

最长下降子序列的标准题，可以当做模板

代码如下：

#include<stdio.h>const int inf=3;int binary_search_1(double ord[],double digit,int head,int length){ int left=head,right=length; int mid; while(right!=left) { mid=(left+right)/2; if(digit==ord[mid]) return mid; else if(digit<ord[mid]) right=mid; else left=mid+1; } return left;}int binary_search_2(double ord[],double digit,int head,int length){ int left=head,right=length; int mid; while(right!=left) { mid=(left+right)/2; if(digit==ord[mid]) return mid; else if(digit>ord[mid]) right=mid; else left=mid+1; } return left;}int main(){ int n; int i,j; int max; int m; double h[1001],ord[1001]; int len_LIS,len_LDS; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) { scanf("%lf",&h[i]); } max=0; for(m=1;m<=n;m++) { ord[0]=-1; len_LIS=1; for(i=1;i<=m;i++) { ord[len_LIS]=inf; j=binary_search_1(ord,h[i],0,len_LIS); if(j==len_LIS) len_LIS++; ord[j]=h[i]; } len_LIS--; ord[m]=inf; len_LDS=1; for(i=m+1;i<=n;i++) { ord[m+len_LDS]=-1; j=binary_search_2(ord,h[i],m,m+len_LDS); if(j==m+len_LDS) len_LDS++; ord[j]=h[i]; } len_LDS--; if(max<len_LIS+len_LDS) max=len_LIS+len_LDS; } PRintf("%d/n",n-max); } return 0;}

上一篇：数据结构实验之串三：KMP应用

下一篇：Bzoj 1066: [SCOI2007]蜥蜴(最大流)