Re: [理工] [資結]中央98-資工所

[privatewind (傷神客)]

※ 引述《luckyburgess (心安即自在)》之銘言：
: 想問第5題的解答
: http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_98_01.pdf
: 麻煩幫我解答一下 !!感謝囉!
標準的DP題目
(1)
A[i]=x0+x1+...+xi, 即A[i]為x0到xi的總和

由此不難推知以下的遞迴式:
if i =0, A[i]= x[0];
if i!=0, A[i]= A[i-1]+ x[i];
用for loop即可在O(n)得出上述A陣列

A[0]=x[0];
for(i=1 ; i< n ;++i){  //n 為A陣列大小
        A[i]=A[i-1]+x[i];
}


(2)
d[i,j]=x_{i}+x_{i+1}+x_{i+2}+...+x{j}
      =x_{0}+x_{1}+...+x{j} - ( x_{0}+x_{1}+...+x_{i-1} )
      =A[j]-A[i-1]
以上用for loop可在O(n^2)內解決
for(i=0 ; i<n; ++i){
        for(int j=i; j<n ;++j){
                if(i==0){
                        d[i][j]=A[j];
                }
                else{
                        d[i][j]=A[j]-A[i-1];
                }
        }
}

綜合(1)(2), 整體複雜度O(n^2), 為其所求。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 120.107.174.109
推 ie925155:為什麼(2)可在big-(n^2)解掉
→ privatewind:寫程式 用兩層迴層就可以KO
推 luckyburgess:謝囉^^
※ 編輯: privatewind     來自: 120.107.174.109      (03/20 00:50)
→ privatewind:補上C code
推 assassin88:x_{0}+x_{1}+...+x{j} - ( x_{0}+x_{1}+...+x_{i-1} )
→ assassin88:這個怎推的??
推 FRAXIS:展開相減.. 就變成定義了