試題 算法訓(xùn)練 攔截導(dǎo)彈

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

輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。
輸入格式
　　一行，為導(dǎo)彈依次飛來的高度
輸出格式
　　兩行，分別是最多能攔截的導(dǎo)彈數(shù)與要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)
樣例輸入
389 207 155 300 299 170 158 65
樣例輸出
6
2
思路：
從題意中我們知道就是求最多可以攔截的導(dǎo)彈數(shù)，那么就是求最長遞減字串長度。求最少的系統(tǒng)數(shù)，就是求最長非遞減字串的長度。求最長遞減字串長度和聰明的美食家是一樣的道理，我們知道至少可以攔截導(dǎo)彈的次數(shù)為1個(gè)所以初始值為1.我們可以當(dāng)1到i的導(dǎo)彈求最長遞減字串長度，然后不斷的求出最長遞減字串長度。
程序：

n=list(map(int,input().split()))
down=[1 for  i in range(len(n))]#down[i]表示以i+1個(gè)字符結(jié)尾的最長遞減子序列
up=[1 for  i in range(len(n))]  #up[i]表示以i+1個(gè)字符結(jié)尾的最長非遞減子序列

for  i in range(len(n)):#當(dāng)前的導(dǎo)彈高度
    for j in range(i):  #i之前的導(dǎo)彈高度
        if n[i]<=n[j]:
            down[i]=max(down[j]+1,down[i]) #最長遞減子序列
        else:
            up[i]=max(up[j]+1,up[i]) #最長非遞減子序列
print(max(down),max(up),sep="\n")

禁止轉(zhuǎn)載。僅用于自己學(xué)習(xí)。對(duì)程序錯(cuò)誤不負(fù)責(zé)。