2112: 聰明的美食家

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

Description

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

Input

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

Output

一個(gè)整數(shù)，表示吃得爽的次數(shù)

Sample Input

10

3 18 7 14 10 12 23 41 16 24

Sample Output

6

HINT

美味度為0到10000的整數(shù)

n<200000

解析：最長(zhǎng)不下降不連續(xù)子序列。直接求快遞超時(shí)。有O（nlogn）算法。上網(wǎng)百度

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}const int maxn=200010; int n; int a[maxn],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; }

?

總結(jié)

以上是生活随笔為你收集整理的zcmu2112的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。