看完題目第一眼的感覺就是求一個最長不上升子序列 和 最長不下降子序列
O(N^2)一定是跑不過去的 所以要寫個O(NlogN)的算法
結果成功寫挫~
思維難度不大，注意二分容易寫爆炸。

?

#include <cstdio> #include <algorithm> #include <cstring>using namespace std;int n; int num[30005],b[30005]; int Max,MAX;void DOWN(){Max = 1;int j;b[Max] = num[Max];for(int i=2;i<=n;i++){if(num[i]<=b[Max]) j = ++Max;else{int l = 1;int r = Max+1;while(l<r){int m = (l+r)>>1;if(b[m]>=num[i]) l = m+1;else r = m;}j = l;}b[j] = num[i];}/*for(int i=1;i<=Max;i++){printf("b[%d]:%d\n",i,b[i]);}*/MAX=Max; }void UP(){memset(b,0,sizeof(b));Max = 1;int j ;b[Max] = num[Max];for(int i=2;i<=n;i++){if(num[i]>=b[Max]) j=++Max;else{int l = 1;int r = Max+1;while(l<r){int m = (l+r)>>1;if(b[m]<=num[i]) l = m+1;else r = m;}j= l;}b[j] = num[i];}/*for(int i=1;i<=Max;i++){printf("b[%d]:%d\n",i,b[i]);}*/MAX = max(Max,MAX); }int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&num[i]);DOWN();UP();printf("%d\n",n-MAX);return 0; }

?

轉載于:https://www.cnblogs.com/OIerLYF/p/7496131.html

總結

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

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