原題鏈接：P1005 [NOIP2007 提高組] 矩陣取數(shù)游戲 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)

摘要

????????有一n*m的矩陣，對(duì)于第i行，每次取走一個(gè)端點(diǎn)值a，同時(shí)此行分?jǐn)?shù)增加a*(2^k)，k代表第k次取數(shù)。求n行最大得分總和。

分析

? ? ? ?1.?容易得知，每一行得分都是獨(dú)立的，不會(huì)影響其他行，因此只要確保每行自己得分最大，則總和得分便是最大[最優(yōu)子結(jié)構(gòu)]。同時(shí)由于每行得分獨(dú)立計(jì)算，因此我們可以每讀取一行時(shí)就直接進(jìn)行計(jì)算，可以減少時(shí)間空間復(fù)雜度(雖然沒什么用就是了= =)

????????2.數(shù)據(jù)范圍小于等于80，2^80遠(yuǎn)超longlong，所以需要高精。

流程

????????運(yùn)用區(qū)間DP思想，用?F[i][j]?表示區(qū)間?[i, j]?可獲得的最大分?jǐn)?shù)。

????????進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)，轉(zhuǎn)移到區(qū)間?[i, j]?的上一區(qū)間必定是?[i-1, j] 或者?[i, j+1]。同時(shí)獲得分?jǐn)?shù)a*(2^k)，且?k=m-(j-i+1)，因此我們很容易得到狀態(tài)轉(zhuǎn)移方程：

F[i][j] = max(F[i][j + 1] + 2^(m - j + i - 1) * arr[j + 1],?

???????????????????? F[i - 1][j] + 2^(m - j + i - 1) * arr[i - 1]);?

代碼實(shí)現(xiàn)

????????首先關(guān)于高精度，先分享一下網(wǎng)上抄的高精模板：

????????但一般沒啥用...而且效率太低，雖然也能過。但我們有更簡單的方法。

????????那就是：__int128?。。?/strong>

????????note：__int128僅64位GCCG++支持，不在C++標(biāo)準(zhǔn)中！不在namespace std中！但64位GCC可直接使用[如果你本地編譯器無法使用，可以使用洛谷在線IDE測試](洛谷在線 IDE (luogu.com.cn))

????????顧名思義，__int128就是占用128字節(jié)的整數(shù)存儲(chǔ)類型，由于是二進(jìn)制，所以范圍是?-2^127~2^127-1，如果使用 unsigned __int128，則范圍變成?0^128，即約39位整數(shù)！足以滿足本體要求。

????????但關(guān)于其具體使用方法本問不再過多介紹。

????????關(guān)鍵代碼：

????????最終代碼（粘板子特供）：

????????（我是不是寫的有點(diǎn)爛啊，不知道說得清不清楚= =但絕對(duì)不是我懶！哼?。?br>