有一排人，身高可能不同，現在有一個理想狀態是這排的每個人向左或向右看沒有被擋住視野(當遇到等高或更高的人時會被擋住)，現在問最少讓幾人出列可以達到這個理想狀態。

最少人出列，其實就是一個人數最多的理想狀態。求一個人數最多的類似"山峰"的高度排列。那就可以從左到右、從右到左各求一遍LIS

?

開始用 O(n²)的寫法WA了，錯在搞錯dp[i] 的含義，dp[i]代表以i為尾的LIS，最后輸出答案時應該枚舉 dp[i]+dp[j]

1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 int height[1024]; 6 int dp1[1024];//up 7 int dp2[1024];//down 8 9 int main(){ 10 int N; 11 scanf("%d",&N); 12 for(int i=0;i<N;++i){ 13 double tmp; 14 scanf("%lf",&tmp); 15 height[i]=tmp*100000+0.1; 16 } 17 for(int i=0;i<N;++i){ 18 dp1[i]=1; 19 for(int j=0;j<i;++j){ 20 if(height[j]<height[i]) dp1[i]=max(dp1[i],dp1[j]+1); 21 } 22 } 23 for(int i=N-1;i>=0;i--){ 24 dp2[i]=1; 25 for(int j=N-1;j>i;--j){ 26 if(height[j]<height[i]) dp2[i]=max(dp2[i],dp2[j]+1); 27 } 28 } 29 //for(int i=0;i<N;++i) printf("i : %d\tup: %d , down: %d\n",i,dp1[i],dp2[i]); 30 int ans=-1; 31 //ans=max(ans,dp2[0]); 32 //for(int i=0;i<N-1;++i)ans=max(ans,dp1[i]+dp2[i+1]); 33 //ans=max(ans,dp1[N-1]); 34 for(int i=0;i<N;++i) 35 for(int j=i+1;j<N;++j) 36 ans=max(ans,dp1[i]+dp2[j]); 37 printf("%d\n",N-ans); 38 } View Code

?

用O(nlogn)的寫法

1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int INF=0x3f3f3f3f; 6 int height[1024]; 7 int dp1[1024];//up 8 int dp2[1024];//down 9 int S[1024]; 10 int tot; 11 12 int B_S(int l,int r,int ob){ 13 int mid; 14 r--; 15 while(l<=r){ 16 mid=(l+r)>>1; 17 if(S[mid]>ob) r=mid-1; 18 else l=mid+1; 19 } 20 return l; 21 } 22 23 int main(){ 24 int N; 25 scanf("%d",&N); 26 for(int i=0;i<N;++i){ 27 double tmp; 28 scanf("%lf",&tmp); 29 height[i]=tmp*100000+0.1; 30 } 31 32 fill(S,S+N,INF); 33 for(int i=0;i<N;++i){ 34 int pos=lower_bound(S,S+N,height[i])-S; 35 dp1[i]=pos+1; 36 S[pos]=height[i]; 37 } 38 fill(S,S+N,INF); 39 for(int i=N-1;i>=0;i--){ 40 int pos=lower_bound(S,S+N,height[i])-S; 41 dp2[i]=pos+1; 42 S[pos]=height[i]; 43 } 44 //for(int i=0;i<N;++i) printf("i : %d\tup: %d , down: %d\n",i,dp1[i],dp2[i]); 45 int ans=-1; 46 //ans=max(ans,dp2[0]); 47 //for(int i=0;i<N-1;++i)ans=max(ans,dp1[i]+dp2[i+1]); 48 //ans=max(ans,dp1[N-1]); 49 for(int i=0;i<N;++i) 50 for(int j=i+1;j<N;++j) 51 ans=max(ans,dp1[i]+dp2[j]); 52 printf("%d\n",N-ans); 53 } View Code 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 int height[1024]; 6 int dp1[1024];//up 7 int dp2[1024];//down 8 int S[1024]; 9 int tot; 10 11 int B_S(int l,int r,int ob){ 12 int mid; 13 r--; 14 while(l<=r){ 15 mid=(l+r)>>1; 16 if(S[mid]>ob) r=mid-1; 17 else l=mid+1; 18 } 19 return l; 20 } 21 22 int main(){ 23 int N; 24 scanf("%d",&N); 25 for(int i=0;i<N;++i){ 26 double tmp; 27 scanf("%lf",&tmp); 28 height[i]=tmp*100000+0.1; 29 } 30 tot=0; 31 for(int i=0;i<N;++i){ 32 if(tot==0||S[tot-1]<height[i]) S[tot++]=height[i]; 33 else{ 34 //int pos=B_S(0,tot,height[i]); 35 int pos=lower_bound(S,S+tot,height[i])-S; 36 S[pos]=height[i]; 37 } 38 dp1[i]=tot; 39 } 40 tot=0; 41 for(int i=N-1;i>=0;i--){ 42 if(tot==0||S[tot-1]<height[i]) S[tot++]=height[i]; 43 else{ 44 //int pos=B_S(0,tot,height[i]); 45 int pos=lower_bound(S,S+tot,height[i])-S; 46 S[pos]=height[i]; 47 } 48 dp2[i]=tot; 49 } 50 //for(int i=0;i<N;++i) printf("i : %d\tup: %d , down: %d\n",i,dp1[i],dp2[i]); 51 int ans=-1; 52 //ans=max(ans,dp2[0]); 53 //for(int i=0;i<N-1;++i)ans=max(ans,dp1[i]+dp2[i+1]); 54 //ans=max(ans,dp1[N-1]); 55 for(int i=0;i<N;++i) 56 for(int j=i+1;j<N;++j) 57 ans=max(ans,dp1[i]+dp2[j]); 58 printf("%d\n",N-ans); 59 } View Code

一種單調棧，一種從修改預設數組，都是二分

開始一直在用upper_bound，后來腦補跑數據才發現，upper_bound只能用來找不下降子序列，lower_bound是用來找嚴格上升子序列。

轉載于:https://www.cnblogs.com/Kiritsugu/p/9581702.html

總結

以上是生活随笔為你收集整理的POJ 1836 Alignment的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。