題目描述

某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。

輸入導(dǎo)彈依次飛來的高度，計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

輸入格式

一行，若干個整數(shù)，中間由空格隔開。

輸出格式

兩行，每行一個整數(shù)，第一個數(shù)字表示這套系統(tǒng)最多能攔截多少導(dǎo)彈，第二個數(shù)字表示如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

輸入輸出樣例

輸入 #1復(fù)制

389 207 155 300 299 170 158 65

輸出 #1復(fù)制

6
2

說明/提示

對于前?50%50%?數(shù)據(jù)（NOIP 原題數(shù)據(jù)），滿足導(dǎo)彈的個數(shù)不超過?104104?個。該部分?jǐn)?shù)據(jù)總分共?100100?分?？墒褂?#xfffd;(�2)O(n2)?做法通過。
對于后?50%50%?的數(shù)據(jù)，滿足導(dǎo)彈的個數(shù)不超過?105105?個。該部分?jǐn)?shù)據(jù)總分也為?100100?分。請使用?�(�log?�)O(nlogn)?做法通過。

對于全部數(shù)據(jù)，滿足導(dǎo)彈的高度為正整數(shù)，且不超過?5×1045×104。

此外本題開啟 spj，每點(diǎn)兩問，按問給分。

---

upd?2022.8.24upd?2022.8.24：新增加一組 Hack 數(shù)據(jù)。

題目簡化

給定一個數(shù)列?�b，問：

1. 它的最長不上升子序列長度；
2. 最少能被劃分成多少個不上升子序列。

#include<bits/stdc++.h>
using namespace std;
int f[1000005],a[100005],maxn,t,v[1000005],l;
int main() {while(cin>>a[++t]);t--;for(int i=1; i<=t; i++) {f[i]=1;for(int j=l; j>0; j--) {if(a[i]<=a[v[j]]) {f[i]=f[v[j]]+1;break;}}l=max(l,f[i]);v[f[i]]=i;maxn=max(maxn,f[i]);}cout<<maxn<<endl;maxn=0;l=0;for(int i=1; i<=t; i++) {f[i]=1;for(int j=l; j>0; j--) {if(a[i]>a[v[j]]) {f[i]=f[v[j]]+1;break;}}l=max(l,f[i]);v[f[i]]=i;maxn=max(maxn,f[i]);}cout<<maxn;
}

?