前言

再做幾題動(dòng)態(tài)規(guī)劃我們就去做圖搜索，另外最近要期中考因?yàn)檫€是需要績(jī)點(diǎn)的，所以斷更幾天。期中考后應(yīng)該就開(kāi)始圖搜索算法啦！
隱約記得這題當(dāng)作期末或者期中考的題目，應(yīng)該是算法的，至少當(dāng)時(shí)我是沒(méi)有做出來(lái)的，現(xiàn)在我憑自己的實(shí)力做出來(lái)了O(n²)，雖然沒(méi)有很快做出來(lái)卡了好久，但是至少進(jìn)步是很明顯的！然后又學(xué)習(xí)了一下貪心的思想也是做出來(lái)O(lgn)！希望跟著我刷題的寶子們跟著我的進(jìn)度也能有大的進(jìn)步！

題目

題目描述

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

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

輸入格式

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

輸出格式

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

樣例 #1

樣例輸入 #1

389 207 155 300 299 170 158 65

樣例輸出 #1

6
2

提示

對(duì)于前 $50\%$ 數(shù)據(jù)（NOIP 原題數(shù)據(jù)），滿(mǎn)足導(dǎo)彈的個(gè)數(shù)不超過(guò) $10^4$ 個(gè)。該部分?jǐn)?shù)據(jù)總分共 $100$ 分?？墒褂?span id="ieo6y2aa" class="katex--inline">$\mathcal{O}(n^2)$ 做法通過(guò)。
對(duì)于后 $50\%$ 的數(shù)據(jù)，滿(mǎn)足導(dǎo)彈的個(gè)數(shù)不超過(guò) $10^5$ 個(gè)。該部分?jǐn)?shù)據(jù)總分也為 $100$ 分。請(qǐng)使用 $\mathcal{O}(n\log n)$ 做法通過(guò)。

對(duì)于全部數(shù)據(jù)，滿(mǎn)足導(dǎo)彈的高度為正整數(shù)，且不超過(guò) $5\times 10^4$。

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

---

$\text{upd?2022.8.24}$：新增加一組 Hack 數(shù)據(jù)。

題目分析

??拋開(kāi)第二問(wèn)，我們先來(lái)關(guān)于第一問(wèn)，也就是第一行的輸出。
??題目第一問(wèn)很明顯是一個(gè)最長(zhǎng)非遞增子序列的計(jì)算或者說(shuō)最長(zhǎng)非嚴(yán)格遞減子串。我給出了兩個(gè)方法，一個(gè)是動(dòng)態(tài)規(guī)劃，但是由于我的技術(shù)不精或者說(shuō)確實(shí)沒(méi)辦法，只能達(dá)到O(n²)。另一種是貪心+二分，就可以達(dá)到O(nlgn)。
??首先介紹一下動(dòng)態(tài)規(guī)劃方法，與我前面的挖地雷類(lèi)似，首先找到數(shù)值變化的點(diǎn)在哪：顯然是找到一個(gè)更小的值可以加到這個(gè)非遞增子序列上。但是我們需要找到最好的值，所以我們建立一個(gè)f數(shù)組，用來(lái)存儲(chǔ)當(dāng)前節(jié)點(diǎn)的最好結(jié)果，然后我們遇到下一個(gè)點(diǎn)的時(shí)候就可以更新包括這個(gè)節(jié)點(diǎn)的最好結(jié)果，如此下去直到最后一個(gè)節(jié)點(diǎn)，然后遍歷整個(gè)f數(shù)組，找到最好的值輸出。具體代碼見(jiàn)下方，但是不足是時(shí)間復(fù)雜度不太行
??接著我們思考貪心的算法，貪心好像需要滿(mǎn)足一個(gè)前提條件局部最優(yōu)解是全局最優(yōu)解的一部分，我這里就不證明了(我也不太會(huì))。直接來(lái)看貪心的思想。對(duì)于每個(gè)數(shù)，既可以把它接到已有的導(dǎo)彈攔截后面，也可以建立一個(gè)新系統(tǒng)。要使子序列數(shù)最少，應(yīng)盡量不建立新序列。另外，應(yīng)讓每個(gè)導(dǎo)彈系統(tǒng)的末尾盡可能大，這樣能接的數(shù)更多。因?yàn)橐粋€(gè)數(shù)若能接到小數(shù)后面，必然能接到大數(shù)后面，反之則不成立。我們維護(hù)一個(gè)棧，用來(lái)表示最長(zhǎng)非遞增子序列，根據(jù)貪心算法的思想這個(gè)棧的維護(hù)需要做到以下兩點(diǎn)：1.比棧頂小的數(shù)直接入棧；2.找到棧里最小的大于該數(shù)的元素，將這個(gè)元素替換成這個(gè)數(shù)。又因?yàn)檫@個(gè)棧是從大到小排序，所以我們找位置的時(shí)候可以使用二分查找來(lái)節(jié)省時(shí)間。代碼也是看下方。
??接著就是解決第二問(wèn)的問(wèn)題，首先需要引入一個(gè)Dilworth定理:

Dilworth定理：對(duì)于任意有限偏序集，其最大反鏈中元素的數(shù)目必等于最小鏈劃分中鏈的數(shù)目。

??換句話講，最長(zhǎng)上升子序列的長(zhǎng)度就是能構(gòu)成的不上升序列的個(gè)數(shù)。于是系統(tǒng)求個(gè)數(shù)其實(shí)就是求最長(zhǎng)遞增子序列或者說(shuō)LIS的長(zhǎng)度，然后按照上面的方法修改一下大于和小于等于號(hào)就可以了！是不是很奇妙，所以這題還是很有難度的，但凡你不知道這個(gè)定理，想要做出來(lái)不是一件容易的事情。

注意事項(xiàng)

1.輸入沒(méi)有給定長(zhǎng)度的處理辦法
C++

int x,n=-1;
while(cin>>x)a[++n]=x;++n;//從0開(kāi)始，n表示個(gè)數(shù)int x,n=0;
while(cin>>x)a[++n]=x;//從1開(kāi)始，n表示個(gè)數(shù)//不知道為什么while(cin>>a[n++]);不行

C語(yǔ)言

while(~scanf("%d",&a[++n])); --n;
while (scanf("%d", a+(++n)) != EOF) ; --n;

python(待補(bǔ)充)

#有沒(méi)有帥哥美女知道的評(píng)論區(qū)告訴我一下

2.注意是最長(zhǎng)非嚴(yán)格遞減數(shù)列，所以是可以包括等于的情況，判斷時(shí)應(yīng)該是a[j]>=a[i]

3.二分法while里面記得判斷條件是a[i]>f[mid]，有個(gè)笨蛋寫(xiě)成a[i]>f[point]了。

代碼

動(dòng)態(tài)規(guī)劃（NOIP要求：時(shí)間復(fù)雜度O(n²)）

NOIP的要求是O(n²)，所以我們可以使用動(dòng)態(tài)規(guī)劃過(guò)前十個(gè)點(diǎn)的數(shù)據(jù)

#include<iostream>
using namespace std;
int a[100007]= {0},path[27]= {0},f1[100007]= {0},f2[100007]= {0};
int main()
{int n=-1,maxx=0,minn=0,flag1=0,flag2=0,x;while(cin>>x)a[++n]=x;++n;f1[0]=1;f2[0]=1;for(int i=1; i<n; i++) {maxx=0;minn=0;//每次都要重新初始化for(int j=0; j<i; j++) {if(f1[j]>maxx&&a[i]<=a[j]) {//找到符合條件的最大值maxx=f1[j];}if(f2[j]>minn&&a[i]>a[j]) {minn=f2[j];}}f1[i]=maxx+1;f2[i]=minn+1;}int ans1=0,ans2=0;for(int i=0; i<n; i++) {if(f1[i]>ans1)ans1=f1[i];if(f2[i]>ans2)ans2=f2[i];}cout<<ans1<<endl<<ans2;return 0;
}

貪心+二分（O(nlgn)）

本法巧妙利用了貪心的性質(zhì)，并且用二分法來(lái)查找最大值，將時(shí)間復(fù)雜度打到O(nlgn)。
并且有個(gè)偷懶的地方是使用了一個(gè)判斷函數(shù)，將兩個(gè)計(jì)算子串長(zhǎng)度的函數(shù)合并成一個(gè)！
棧還保存了最長(zhǎng)上升或遞減子序列的列表

噔噔噔！代碼閃亮登場(chǎng)！

#include<iostream>
using namespace std;int a[100007]= {0},f[100007]= {0};
void test(int f[],int x){//沒(méi)有用就是用來(lái)測(cè)試的 for(int i= 1; i<=x;i++){cout<<f[i]<<" ";}cout<<endl;
}
bool relation(int x,int y,int rela)//用來(lái)返回判斷值的 
{if(rela==1) {return x>y;} elsereturn x<=y;
}
int Lg_sequence(int n,int rela)//計(jì)算相反的兩個(gè)最長(zhǎng)子串 
{int f[100007]= {0};int point=1;f[1]=a[0];for(int i = 1 ; i < n ; i ++) {if(relation(a[i],f[point],rela)) {//符合子串直接入棧 f[++point]=a[i];} else {int l = 1, r = point;while (l < r) {//找到大于該值的最小的棧值 int mid = (l + r) >> 1;if (relation(a[i],f[mid],!rela)) {r = mid;} else {l = mid + 1;}}f[l] = a[i];}}return point;
}
int main()
{int n=-1,maxx=0,minn=0,point=1,x;while(cin>>x)a[++n]=x;++n;//n表示數(shù)組長(zhǎng)度 cout<<Lg_sequence(n,0)<<endl<<Lg_sequence(n,1);return 0;
}

后話

額外測(cè)試用例

因?yàn)樘揩@得了兩個(gè)測(cè)試用例

樣例輸入 #1

330 309 267 287 315 380 365 363 364 351 316 381 355 372 289 284 356 299 369 361 327 372 360 282 327 280 258 293 258 254 298 320 324 314 273 340 251 324 327 339 270 248 275 318 321 283 293 341 247 321 318 270 328 322 294 299 259 304 302 286 287 239 333 300 269 240 269 275 296 292 254 308 325 285 218 282 221 288 238 307 212 263 316 300 264 278 215 304 306 296 218 206 225 206 266 250 288 208 241 297 264 211 285 294 236 206 292 215 249 195 206 202 198 276 258 199 192 207 195 261 253 212 206 214 269 234 254 250 196 246 244 227 229 238 194 221 192 243 181 233 180 242 206 247 223 195 187 210 181 176 214 201 209 207 231 222 199 217 212 222 197 168 217 195 193 216 163 203 163 230 206 201 153 184 177 193 174 189 175 155 148 197 184 201 169 155 182 166 156 202 204 193 143 199 167 194 174 195 181 171 163 170 173 169 184 160 130 132 166 128 160 149 140 182 144 127 140 175 134 175 146 169 159 176 152 118 131 120 156 119 141 144 121 146 116 160 136 116 123 135 109 158 127 115 127 148 116 126 140 109 129 122 123 120 109 114 134 98 95 133 108 108 124 115 99 92 97 132 106 116 115 120 116 123 91 94 107 115 114 110 98 81 94 109 114 86 92 97 105 107 94 98 79 93 83 96 70 71 88 71

樣例輸出 #1

69
11

樣例輸入 #2

90 103 99 83 102 70 86 70 99 71

樣例輸出 #2

5
3

王婆賣(mài)瓜

感覺(jué)有收獲或者想跟上我的進(jìn)度刷題的，可以點(diǎn)個(gè)關(guān)注，或者點(diǎn)贊收藏評(píng)論都可以！

參考來(lái)源

NOIP 1999 普及組
洛谷題目-傳送門(mén)
參考材料-TernaryTree