題目鏈接

石子合并

image.png

image.png

有限集。
是有限的
一開始有n - 1種選法(一共有n堆)，第二次是n - 2種選法(一共有n - 1堆)。。。。

image.png

狀態(tài)表示：所有將[i, j]這一段合并成一堆的方案的集合。一共有（j - i + 1）堆，所以方案數(shù)是(j - i)!個(gè)。

如何狀態(tài)分類？

以最后一次合并時(shí)候的分界點(diǎn)k來(lái)劃分。
也就是左邊的最后一堆是哪一堆來(lái)劃分。

image.png

左邊的最后一堆可以是第i堆，也就是左邊只有1堆。
左邊的最后一堆可以是第i + 1堆，也就是左邊有2堆。
...
左邊的最后一堆可以是第j - 1堆，因?yàn)槠鸫a得有兩堆，所以這樣的結(jié)果是右邊這一堆只有1個(gè)，也就是第j堆。

image.png

枚舉的順序是先枚舉區(qū)間長(zhǎng)度len，len從2開始，因?yàn)閘en為1表示只有1堆，1堆是合并不了的，代價(jià)也是0，加上全局變量初值為0，所以len可以從2開始枚舉。
枚舉區(qū)間左端點(diǎn)
右端點(diǎn)是
因?yàn)榈谌匮h(huán)，是枚舉不同k中的最小值，所以要將f[i][j]的初始值定義為2e9，不然狀態(tài)轉(zhuǎn)移的結(jié)果都是0，不能正確的進(jìn)行狀態(tài)轉(zhuǎn)移。
f[1][n]表示所有將[1, n]合并成1堆的集合中的最小代價(jià)。

image.png

f[i][j]設(shè)置成2e9后，作用的是右下角那里，紅色箭頭指向。

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

cpp代碼

#include <iostream>

using namespace std;

const int N = 310;

int n;
int a[N], s[N];
int f[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];
    
    f[0][0] = 0;
    for(int len = 2; len <= n; len ++)
        for(int i = 1; i + len - 1 <= n; i ++)
        {
            int j = i + len - 1;
            f[i][j] = 2e9;
            for(int k = i; k <= j - 1; k ++)
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
        
    cout << f[1][n] << endl;
    
    return 0;
}

核心：只能合并的是相鄰兩堆，如果沒有這個(gè)限制，就變成了一個(gè)貪心的問題，比如合并果子。

image.png