767
最長不下降子序列 jobdu 1112
題目描述：
某國為了防禦敵國的導彈襲擊，開發出一種導彈攔截係統。但是這種導彈攔截係統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲，並觀測到導彈依次飛來的高度，請計算這套係統最多能攔截多少導彈。攔截來襲導彈時，必須按來襲導彈襲擊的時間順序，不允許先攔截後麵的導彈，再攔截前麵的導彈。
輸入：
每組輸入有兩行，
第一行，輸入雷達捕捉到的敵國導彈的數量k（k<=25），
第二行，輸入k個正整數，表示k枚導彈的高度，按來襲導彈的襲擊時間順序給出，以空格分隔。
輸出：
每組輸出隻有一行，包含一個整數，表示最多能攔截多少枚導彈。
樣例輸入：
8
300 207 155 300 299 170 158 65
樣例輸出：
6
dp[i]表示data[i]作為子序列結尾時的最長子序列長度。
dp[i]=1+max{dp[j] | data[j]>=data[i] 且 0<=j<i },並不是往前第一個不小於data[i]的數字！
時間複雜度為O(n^2)
最後更新：2017-04-03 12:55:19