P1880 [NOI1995] 石子合并

/*
在一個圓形操場的四周擺放 N 堆石子，現要將石子有次序地合并成一堆，
規定每次只能選相鄰的 2 堆合并成新的一堆，并將新的一堆的石子數，記為該次合并的得分。
試設計出一個算法,計算出將 N 堆石子合并成 1 堆的最小得分和最大得分。

洛谷題號：P1880    https://www.luogu.com.cn/problem/P1880

*/

/*
狀態轉移方程
dp[i][j]:表示將第i~j對石子合并為一堆石子的最小得分
dp[i][j]= min( dp[i][k] + dp[k+1][j] )  (i <= k < j)
k是某個分界點，左邊一堆 i~k 的最小得分就是dp[i][k]，右邊一堆 k+1~j 的最小得分是dp[k+1][j]
狀態轉移方程需要結合分析圖來看，分析圖參考同目錄下的 '11 石子合并問題.png'
*/

// 這里先用遞歸方式來實現上述動態轉移方程
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;


int a[100] = {0};                    //前綴和，可以簡化第1堆石子的總分數求和
int dp[100][100] = {0};

int stoneMerge(int l, int r) {
    //邊界值

    if(l == r) return 0; //只有一堆的情況無需再分堆
    if(dp[l][r]>0) return dp[l][r];
    
    int ans = INT_MIN;
    for (int k = l; k < r; k++) {
        ans = max(ans, stoneMerge(l, k) + stoneMerge(k + 1, r));
    }

    ans += (a[r] - a[l - 1]);
    
    dp[l][r] = ans;
    return dp[l][r];
}
//l表示起始堆好，r表示末尾堆號


/*測試數據
    7
    13
    7
    8
    16
    21
    4
    18
*/
int main(void) {
    int n = 0;//輸入的整數的個數
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    int minScore = stoneMerge(1, n);
    cout << "\n" << minScore;
    return 0;
}