学步园

最长递增子序列的应用。从前往后跑一遍，然后从后往前跑一遍。最后枚举。

#include <algorithm><br /> #include <iostream><br /> template<class T> void Get_Max(T& a,T b)<br /> { if(a<b) a=b;}<br /> using namespace std;<br /> double height[1005],temp_height;<br /> double min_height[1005];<br /> int cnt[1005],cnt2[1005];<br /> int Find(int len,double height)//min_height[mid-1]<height[i]<=min_height[mid]<br /> {<br /> int left=0,right=len;<br /> int mid;<br /> while(left<=right)<br /> {<br /> mid=(left+right)/2;<br /> if(height>min_height[mid]) left=mid+1;<br /> else if(height<min_height[mid]) right=mid-1;<br /> else return mid;//如果改成是非严格递增子序列，是不是应该return mid+1;<br /> }<br /> return left;<br /> }<br /> int main()<br /> {<br /> int n;<br /> int ans;<br /> scanf("%d",&n);<br /> for(int i=0;i<n;i++)<br /> {<br /> scanf("%lf",&height[i]);<br /> }<br /> int len=0;<br /> fill(min_height,min_height+1005,10000);<br /> min_height[0]=-1;<br /> for(int i=0;i<n;i++)//从前往后lis<br /> {<br /> int j=Find(len,height[i]);//min_height[j-1]<height[i]<=min_height[j]<br /> min_height[j]=height[i];<br /> if(j>len) len=j;<br /> cnt[i]=len;<br /> }<br /> len=0;<br /> fill(min_height,min_height+1005,10000);<br /> min_height[0]=-1;<br /> for(int i=n-1;i>=0;i--)//从后往前lis<br /> {<br /> int j=Find(len,height[i]);<br /> min_height[j]=height[i];<br /> if(j>len) len=j;<br /> cnt2[i]=len;<br /> }<br /> ans=0;<br /> for(int i=0;i<n-1;i++)//枚举分解点<br /> {<br /> Get_Max(ans,cnt[i]+cnt2[i+1]);<br /> }<br /> ans=n-ans;<br /> printf("%d/n",ans);<br /> return 0;<br /> }<br />