【正文】 / 剩余未求解元素個(gè)數(shù) if(!res_arr[i]) count++。 backtrack(i+1,k)。amp。) break。 if(0==w) flag=false。 // 當(dāng)前求解最大值 bool input(){ bool flag=true。bool* nVisited=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool))。每行由若干個(gè)整數(shù)構(gòu)成，第一個(gè)整數(shù)為所購(gòu)買的木塊的長(zhǎng)度L（0L=30000）,第二個(gè)整數(shù)為鋸子的寬度W（0W=1000）,其后的若干個(gè)整數(shù)分別表示制作家具時(shí)需要的木塊的長(zhǎng)度。}void solve(){ memset(dp,0,sizeof(dp))。i++){ if(nextJ[i][j]!=j){ (i)。jj++){ // 計(jì)算離開電梯的人和留在電梯里面的人中到達(dá)目的地最晚的 int tmp=max(tStay(i,j,jj),tLeave(i,jj+1,j))。j++){ // 1,j表示停靠請(qǐng)求的編號(hào),編號(hào)越小表示編號(hào)?？繕菍釉礁? dp[topFloor][j]=tLeave(topFloor,1,j)。// 目前電梯在第currF層, 第L層到第R層乘客離開電梯// 函數(shù)返回這些離開電梯的乘客中最晚到達(dá)目的層所需時(shí)間int tLeave(int currF,int l,int r){ if(lr) return 0。int n,f[maxN+1]。使用i,j兩個(gè)參數(shù)表示電梯當(dāng)前的狀態(tài)，即電梯在第i層，電梯中有j位乘客。由于去各個(gè)樓層的具體數(shù)目對(duì)結(jié)果沒有影響，所以可以將“電梯還剩i個(gè)人”表述成“電梯里面的乘客還要去i個(gè)樓層”。在分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。對(duì)于此測(cè)試用例電梯?？坑?jì)劃方案：4 10，這樣到第4樓的乘客所需時(shí)間為3*4=12秒，到第5樓的乘客所需時(shí)間為3*4+20=32秒，到第10樓的乘客所需時(shí)間為9*4+10=46秒，即最后到達(dá)目的樓層的顧客所需時(shí)間為46秒。輸出要求：對(duì)于每一個(gè)測(cè)試用例，第1行輸出最后一位乘客到達(dá)目的樓層所需時(shí)間，第2行輸出?？看螖?shù)和相應(yīng)的?？糠桨?，每一個(gè)數(shù)字用一個(gè)空格隔開。不管子問題以后是否被使用，只要他被計(jì)算過，就將其結(jié)果填入表中。決策后，電梯里面的乘客被分成兩部分：乘客留在電梯里面繼續(xù)上升；乘客離開電梯走樓梯到達(dá)。第二步：根據(jù)狀態(tài)轉(zhuǎn)移方程計(jì)算f(i,j)。 // 注意：f[1...n]中樓層數(shù)從高到低排列 for(int i=n。 // 所有人都離開電梯 else if(jj==0) return 0。i){ // i表示電梯此刻所在位置 for(int j=1。 } } } } coutdp[1][n]endl。 } } cout()。 rebuildSolution()。算法具體描述如下：Step 1：聲明求解結(jié)果變量res=0，剩余未切割木料數(shù)量count=n，當(dāng)前已切割木料長(zhǎng)度和cw=0，目前最大切割長(zhǎng)度bestW=0，求解標(biāo)記數(shù)組visited[n]，當(dāng)前最優(yōu)求解數(shù)組nVisited[n]，問題求解狀態(tài)記錄數(shù)組res_arr[n]，鋸口寬度sw；Step 2：當(dāng)剩余未切割木料數(shù)量count大于0時(shí)，利用回溯法進(jìn)行最大子集和求解。 // 原材料長(zhǎng)度 int n。 memset(res_arr,false,MAX_SAMPLE_LENGTH*sizeof(bool))。 while(flag){ scanf(%d,data+n)。 // 記錄當(dāng)前最優(yōu)解 for(int i=0。 // 訪問標(biāo)記 visited[i]=true。 while(count0){ // 初始化,cw當(dāng)前已鋸木頭長(zhǎng)度和, // count剩余未鋸木頭數(shù)量,bestW本次求解最大長(zhǎng)度和 cw=0,count=0,bestW=0。}int main(){ while(input()){ solve(data,n)。2) 逐層向上遞推，最后得到問題的最優(yōu)解根據(jù)題意，待處理的數(shù)據(jù)規(guī)模同數(shù)塔的層數(shù)有關(guān)，同時(shí)數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)與層數(shù)相同，所以可以使用二維數(shù)組data存儲(chǔ)待處理節(jié)點(diǎn)數(shù)值，只有一半的節(jié)點(diǎn)有數(shù)值，實(shí)際上是一個(gè)下三角矩陣。 // dp初始化 for (int i = 0。 j = i。 // 首先輸出塔頂元素 int j = 0,i=0。 if (node_value == dp[index]) ++j。 memset(dp,0,n*n*sizeof(int))。 char ch=getcha