ascal動(dòng)態(tài)規(guī)劃普及組(專(zhuān)業(yè)版)
【正文】 ? 輸入文件 ，分別表示 N， M（ 2=N=10， 1=M=5），第二行是一個(gè)長(zhǎng)度為 N的數(shù)字串。動(dòng)態(tài)規(guī)劃（普及組）三 紹興柯橋中學(xué) 吳建鋒 動(dòng)態(tài)規(guī)劃的應(yīng)用（問(wèn)題 5） ? 導(dǎo)彈攔截。 ? 輸出文件 ，表示求得的最大乘積?，F(xiàn)在要求設(shè)計(jì)一個(gè)程序，以求得正確的答案。某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。 輸入和輸出 ? ? 4 2 ? 1231 ? ? 62 算法分析 ? 本來(lái)用搜索也可 ? n， m擴(kuò)大時(shí)，必須用動(dòng)態(tài)規(guī)劃 ? 用 f[I,j]表示在前 i個(gè)數(shù)字中插入 j個(gè)乘號(hào)可以獲得的最大值，那么 f[n,m]就是問(wèn)題的最優(yōu)解。 ? 同時(shí)，為了幫助選手能夠理解題意，主持人還舉了如下一個(gè)例子： ? 有一個(gè)數(shù)字串： 312，當(dāng) N=3,M=1時(shí)有二種分法： ? （ 1） 3 12＝ 36； ? （
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1