某國(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)的高度（雷達(dá)給出高度數(shù)據(jù)是不大于30000的整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有的導(dǎo)彈最少配備多少套這種導(dǎo)彈系統(tǒng)。
三；問(wèn)題分析：
該系統(tǒng)的第一發(fā)炮彈能夠達(dá)到任意高度，所以要求出系統(tǒng)最多能夠攔截的導(dǎo)彈數(shù)，其實(shí)就是在求一個(gè)最長(zhǎng)的下降序列。要求出系統(tǒng)攔截所有的導(dǎo)彈至少需要配備的套數(shù)，可用貪婪算法，采用數(shù)組記錄導(dǎo)彈數(shù)量和導(dǎo)彈的分類(lèi)，算出數(shù)組的元素個(gè)數(shù)即為系統(tǒng)的套數(shù)。
標(biāo)簽：
防御
導(dǎo)彈
上傳時(shí)間：
2015-04-23
上傳用戶(hù)：R50974
