四边形不等式优化

1. 问题背景
   这是‌石子合并问题‌的优化解法，目标是找到合并n堆石子的最小代价，每次合并相邻两堆，合并代价为两堆石子的重量之和。

2. 四边形不等式优化原理
   ‌朴素DP复杂度‌：O(n)，需要对每个区间枚举所有分割点
   ‌优化后复杂度‌：O(n)，利用了决策点split[i][j]的单调性
   ‌单调性性质‌：split[i][j-1] ≤ split[i][j] ≤ split[i+1][j]

3. 关键数据结构
   prefix数组：前缀和，用于O(1)计算区间和
   dp数组：存储最小合并代价
   split数组：存储最优决策点，是优化的核心

4. 时间复杂度分析
   外层循环：按区间长度递增，O(n)
   内层循环：区间起点遍历，O(n)
   最内层循环：由于四边形不等式的性质，所有区间的k枚举总次数为O(n)
   ‌总复杂度‌：O(n)，相比朴素O(n)有显著提升

5. 注意事项
   数组下标从1开始，方便计算
   k < j条件确保分割点有效
   初始化split[i][i] = i是四边形不等式正确性的基础
   区间和计算：prefix[j] - prefix[i-1]

#include <iostream>
#include <vector>
#include <climits>  // 用于INT_MAX
using namespace std;

int main() {
    int n;
    cin >> n;  // 输入石子堆数
    
    // stones存储每堆石子的重量，prefix存储前缀和
    vector<int> stones(n + 1, 0);      // 下标从1开始
    vector<int> prefix(n + 1, 0);      // prefix[i] = 前i堆石子的总重量
    
    // 读入数据并计算前缀和
    for (int i = 1; i <= n; i++) {
        cin >> stones[i];
        prefix[i] = prefix[i - 1] + stones[i];  // 前缀和递推公式
    }
    
    // dp[i][j]: 合并区间[i,j]的石子所需的最小代价
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    
    // split[i][j]: 使dp[i][j]取最小值的最优分割点k
    // 四边形不等式优化的关键：记录决策点
    vector<vector<int>> split(n + 1, vector<int>(n + 1, 0));
    
    // 初始化：单个石子堆不需要合并，代价为0
    // 同时初始化split[i][i] = i（虽然单个区间不需要分割）
    for (int i = 1; i <= n; i++) {
        split[i][i] = i;  // 单个区间的最优分割点就是自己
    }
    
    // 区间DP：按区间长度从小到大计算
    for (int len = 2; len <= n; len++) {          // 区间长度从2到n
        for (int i = 1; i + len - 1 <= n; i++) {  // 区间起点i
            int j = i + len - 1;                   // 区间终点j
            
            dp[i][j] = INT_MAX;  // 初始化为最大值
            
            // 四边形不等式优化的核心部分：
            // 利用单调性缩小k的搜索范围
            int left = split[i][j - 1];   // 根据四边形不等式性质
            int right = split[i + 1][j];  // k的搜索范围在[left, right]之间
            
            // 在缩小后的范围内枚举分割点k
            for (int k = left; k <= right; k++) {
                if (k < j) {  // 确保k是有效的分割点（k需要严格小于j）
                    // 状态转移方程：
                    // 合并[i,j]的代价 = 合并[i,k]的代价 + 合并[k+1,j]的代价 + 本次合并的代价
                    int val = dp[i][k] + dp[k + 1][j] + prefix[j] - prefix[i - 1];
                    
                    // 更新最小代价和最优分割点
                    if (val < dp[i][j]) {
                        dp[i][j] = val;
                        split[i][j] = k;  // 记录最优决策点
                    }
                }
            }
        }
    }
    
    // 输出合并所有石子堆的最小代价
    cout << dp[1][n] << endl;
    
    return 0;
}