分類：演算法與資料結構
2.5石子合併問題
也有人把這類問題叫做是區間上的動態規劃。
例題22
石子合併
(stone.pas/c/cpp)
**：某年noi（去巴蜀交）
【問題描述】
在乙個操場上擺放著一行共n堆的石子。現要將石子有序地合併成一堆。規定每次只能選相鄰的兩堆合併成新的一堆，並將新的一堆石子數記為該次合併的得分。
請編輯計算出將n堆石子合併成一堆的最小得分和將n堆石子合併成一堆的最大得分。
【輸入檔案】
輸入第一行為n(n<1000)，表示有n堆石子，第二行為n個用空格隔開的整數，依次表示這n堆石子的石子數量（<=1000）
【輸出檔案】
輸出將n堆石子合併成一堆的最小得分和將n堆石子合併成一堆的最大得分。
【輸入樣例】
31 2 3
【輸出樣例】
9 11
【問題分析】
人們那到這類題目的第一想法是貪心（找最大/最小的堆合併），但是很容易找到貪心的反例：（以求最小為例）
貪心：3 4 6 5 4 2
5 4 6 5 4 得分：5
9 6 5 4得分：9
9 6 9得分：9
15 9得分：15
24得分：24
總得分：62
合理方案
3 4 6 5 4 2
7 6 5 4 2 得分：7
7 6 5 6得分：6
7 11 6得分：11
13 11得分：13
24得分：24
總得分：61
也就是說第二個4 和2 合併要比和5合併好，但是由於一開始2被用了沒辦法它只好和5合併了……
既然貪心不行，資料規模有很大，我們自然就想到用動態規劃了。
*不過要知道某個狀態下合併後得分最優就需要知道合併它的總得分，只有對子問題的總得分進行最優的判斷，設計的狀態才有意義。
*但要是想知道總分，就要知道合併一次的得分，顯然這個含義不能加到動態規劃的狀態中，因為一般乙個狀態只代表乙個含義（也就是說opt[i]的值只能量化乙個問題）（上面代*號的兩段比較抽象，不懂可以不看。我只是為了標註自己的理解加的，不理解的也沒必要理解。）
先要把題目中的環變成鏈，這樣好分析問題。具體方法：把環截斷，複製乙份放到截斷後形成的鏈的後面形成乙個長度是原來兩倍的鏈（只有環中的元素在處理時不隨著變化，就可以這樣做。
其實讀入資料已經幫你截斷了）；
例： 3 4 5
變成 3 4 5 3 4 5
對於這樣乙個鏈，我們設計乙個狀態opt[i,j]表示起點為i終點為j的鏈合併成一堆所得到的最優得分。
要合併乙個區間裡的石子無論合併的順序如何它的得分都是這個區間內的所有石子的和，所以可以用一
個陣列sum[i]存合併前i個石子的得分。
因為合併是連續的所以決策就是把某次合併看作是把某個鏈分成兩半，合併這想把兩半的好多堆分別合併成一堆的總得分+最後合併這兩半的得分；
狀態轉移方程：
maxopt[i,j]=max+sum[j]-sum[i-1]
minopt[i,j]=min+sum[j]-sum[i-1]
複雜度：狀態數o（n2）*決策數o（n）=o（n3）
【源**】
program stone;
const
maxn=1010;
vara,sum:array[0..maxn] of longint;
minopt,maxopt:array[0..maxn*2,0..maxn*2] of longint;
n:longint;
minans,maxans:longint;
procedure init;
vari:longint;
begin
read(n);
for i:=1 to n do
begin
read(a[i]);
a[n+i]:=a[i];
end;
for i:=1 to n*2 do
sum[i]:=sum[i-1]+a[i];
end;
function max(x,y:longint):longint;
begin
max:=y;
if x>y then max:=x;
end;
function min(x,y:longint):longint;
begin
min:=y;
if (x0) then min:=x;
end;
procedure main;
vari,j,l,k:longint;
begin
fillchar(minopt,sizeof(minopt),200);
fillchar(maxopt,sizeof(maxopt),0);
for i:=1 to 2*n do
minopt[i,i]:=0;
for l:=1 to n-1 do
for i:=1 to 2*n-l do
begin
j:=i+l;
for k:=i to j-1 do
begin
maxopt[i,j]:=max(maxopt[i,j],maxopt[i,k]+maxopt[k+1,j]);
minopt[i,j]:=min(minopt[i,j],minopt[i,k]+minopt[k+1,j]);
end;
inc(maxopt[i,j],sum[j]-sum[i-1]);
inc(minopt[i,j],sum[j]-sum[i-1]);
end;
maxans:=-maxlongint;
minans:=maxlongint;
for i:=1 to n do
maxans:=max(maxans,maxopt[i,i+n-1]);
for i:=1 to n do
minans:=min(minans,minopt[i,i+n-1]);
end;
begin
init;
main;
writeln(minans,' ',maxans);
end.
動態規劃入門
分類 演算法與資料結構 2.6其他問題 還有一些題目雖和一寫基本模型相似但又有區別，我也就不總結共性了，列出它們，看看他們的狀態又是怎麼設計的 例題25 花店櫥窗設計 flower.pas c cpp ioi或巴蜀評測系統 問題描述 假設以最美觀的方式布置花店的櫥窗，有f束花，每束花的品種都不一樣，...
動態規劃入門詳解
通過金礦模型介紹動態規劃 對於動態規劃，每個剛接觸的人都需要一段時間來理解，特別是第一次接觸的時候總是想不通為什麼這種方法可行，這篇文章就是為了幫助大家理解動態規劃，並通過講解基本的01揹包問題來引導讀者如何去思考動態規劃。本文力求通俗易懂，無異性，不讓讀者感到迷惑，引導讀者去思考，所以如果你在閱讀...
理財規劃入門作業
一 單項選擇題 請從四個備選答案中選擇1個正確的答案，用字母填寫到括號內 l 在理財規劃過程中，屬於客戶職責的是 2005.12專1 a a 提出需求b 編制家庭資產負債表 c 確定理財目標d 經濟環境分析 2 在與客戶的交流溝通中，一般不建議理財規劃師採用 方式進行提問。2005.12專6 a 誘...