聰明的美食家

Time Limit:?1 Sec??Memory Limit:?128 MB Submit:?55??Solved:?12 [Submit][Status][Web Board]

Description

如果有人認為吃東西只需要嘴巴，那就錯了。 都知道舌頭有這么一個特性，“由簡入奢易，由奢如簡難”（據好事者考究，此規律也適合許多其他情況）。具體而言，如果是甜食，當你吃的食物不如前面剛吃過的東西甜，就很不爽了。 大寶是一個聰明的美食家，當然深諳此道。一次他來到某小吃一條街，準備從街的一頭吃到另一頭。為了吃得爽，他大費周章，得到了各種食物的“美味度”。他拒絕不爽的經歷，不走回頭路而且還要爽歪歪（爽的次數盡量多）。

Input

　　兩行數據。 第一行為一個整數n，表示小吃街上小吃的數量 第二行為n個整數，分別表示n種食物的“美味度”

Output

一個整數，表示吃得爽的次數

Sample Input

103 18 7 14 10 12 23 41 16 24

Sample Output

6

HINT

美味度為0到10000的整數 n<200000

#include<bits/stdc++.h> using namespace std; const int maxn = 200010;int n; int a[maxn]; int b[maxn]; int main() {while (~scanf("%d",&n)){for(int i=0; i<n; i++)scanf ("%d",&a[i]);int ans=1;b[0]=a[0];for(int i=1 ; i<n ; i++){if(a[i]>=b[ans-1])b[ans++]=a[i];else{int t=upper_bound(b,b+ans,a[i])-b;b[t]=a[i];}}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的zcmu- 聪明的美食家 最长不连续上升子序列（nlogn）的全部內容，希望文章能夠幫你解決所遇到的問題。

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