区间规划

分石子

有多堆石子，每次合并相邻的两堆，花费石子总重量的力气，要求花费的最小力气

状态表示

把 i 到 j 堆石子合并起来的所有可能的做法集合，要求花费力气的最小值

属性： min

状态计算

以最后一次合并作为分界线，有 n 种情况 那么 f[i][j] = min(f[i][k], f[k + 1][j]) + 最后一步 中的最小可能值，k为最后一次合并的分界线位置，最后一步不管怎么分代价相同

区间规划 2024-03-11 21.29.12.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

i

j

k

Link to original

遍历分界线 k 求最小值。 k 其中 k 最大到 j - 1 （因为右边一定要有剩，k才算是分界线）

实现

//前缀和
    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        s[i] = s[i-1] + s[i];
    }
    
    //枚举区间长度,保证计算时要用到的分类值都计算好
    for(int len = 2; len <= n; len ++)
    //枚举起点,右边界不可以大于n
        for(int i = 1; i + len - 1 <= n; i ++)
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e9;
            for(int k = l; k <= r - 1; 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;