E56【模板】四边形不等式优化DP 石子合并

问题描述

有n堆石子排成一排，每堆石子有一定的数量。每次可以合并相邻的两堆石子，合并后新的石子堆数量为两堆之和，合并的代价为两堆石子之和。求将所有石子合并成一堆的最小总代价。

输入输出格式

输入：
第一行包含一个整数n（1 ≤ n ≤ 1000），表示石子的堆数。
第二行包含n个正整数，分别表示每堆石子的数量。

输出：
一个整数，表示合并所有石子的最小总代价。

思路分析

使用动态规划（DP）解决区间合并问题，设dp[i][j]为合并第i到第j堆石子的最小代价。

• 状态转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum[i][j]，其中sum[i][j]为第i到第j堆石子的总和，k为分割点（i ≤ k < j）。
• 直接DP时间复杂度为O(n³)，通过四边形不等式优化可将时间复杂度降至O(n²)。优化条件：决策点k满足单调性，即opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]，其中opt[i][j]为dp[i][j]的最优分割点。

代码实现

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // 前缀和数组
    vector<int> sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + a[i];
    }
    
    // dp[i][j]表示合并i到j堆的最小代价
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // opt[i][j]表示dp[i][j]的最优分割点k
    vector<vector<int>> opt(n, vector<int>(n, 0));
    
    for (int l = 2; l <= n; ++l) {  // 区间长度
        for (int i = 0; i + l <= n; ++i) {  // 区间起点
            int j = i + l - 1;  // 区间终点
            dp[i][j] = INT_MAX;
            // 决策点范围：opt[i][j-1] <= k <= opt[i+1][j]，初始时opt[i][j]在[i, j-1]范围内
            int start = (i == 0 ? i : opt[i][j-1]);
            int end = (j == n-1 ? j-1 : opt[i+1][j]);
            for (int k = start; k <= end; ++k) {
                int current = dp[i][k] + dp[k+1][j] + sum[j+1] - sum[i];
                if (current < dp[i][j]) {
                    dp[i][j] = current;
                    opt[i][j] = k;
                }
            }
        }
    }
    
    cout << dp[0][n-1] << endl;
    return n;
}

E56【模板】四边形不等式优化DP 石子合并

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=310;
int n, a[N], s[N];
int f[N][N]; //f[i,j]表示合并区间[i,j]的石子的最小代价 

int main(){
  memset(f,0x3f,sizeof(f)); cin>>n;
  for(int i=1;i<=n;i++)
    cin>>a[i], s[i]=s[i-1]+a[i], f[i][i]=0;
  
  for(int len=2; len<=n; len++)         //区间长度
    for(int i=1,j; (j=i+len-1)<=n; i++) //区间端点
      for(int k=i; k<j; k++)            //区间分割点
        if(f[i][j]>f[i][k]+f[k+1][j]+s[j]-s[i-1])
          f[i][j]=f[i][k]+f[k+1][j]+s[j]-s[i-1];
  cout<<f[1][n];
}

// 四边形不等式优化
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1010;
int n, a[N], s[N];
int f[N][N]; //f[i,j]表示合并区间[i,j]的石子的最小代价
int p[N][N]; //p[i,j]记录区间[i,j]的最优分割点

int main(){
  memset(f,0x3f,sizeof(f)); cin>>n;
  for(int i=1; i<=n; i++)
    cin>>a[i],s[i]=s[i-1]+a[i],f[i][i]=0,p[i][i]=i;
  
  for(int len=2; len<=n; len++)               //区间长度
    for(int i=1,j; (j=i+len-1)<=n; i++)       //区间端点
      for(int k=p[i][j-1]; k<=p[i+1][j]; k++) //区间分割点
        if(f[i][j]>f[i][k]+f[k+1][j]+s[j]-s[i-1])
          f[i][j]=f[i][k]+f[k+1][j]+s[j]-s[i-1], p[i][j]=k;
  cout<<f[1][n];
}