石子合并

• 集合： 所有从第 i 堆石子到第 j 堆石子合并成一堆石子的合并方式

• 这道题之所以刚开始要求一次前缀和是为了防止到时候又要计算l~r的总和而浪费时间。
  for (int k = l; k <= r; k ++ ) 不能改成 for (int k = l + 1; k < r; k ++ ) ，这样的话得出的结果都是INF。因为如果len=2这样写就会直接跳过了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

const int N = 310, INF = 1E9;
using namespace std;
int s[N], f[N][N], n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> s[i];
    for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];

    for (int len = 2; len <= n; len ++ )
    {
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;
            f[l][r] = INF;
            for (int k = l; k <= r; k ++ )
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }

    cout << f[1][n] << endl;

    return 0;
}