题解 | #石子合并#

非常经典的区间dp题啊，这种题的数据结构不大，可以从一些比如n3复杂的的方式入手

对于状态转移方程，区间[a,b]与[x,y]合并，代价就是：两个区间之前合并到这一步所记录的代价+他们自己的代价。也就是说我们需要维护两个数组：dp与presum来分别记录路径代价与区间重量总和，对于每个大的区间，可以用经典的选取中间点的方式来转移

dp[l][r] = min(dp[l][r],dp[l][m] + dp[m + 1][r] + sum[l][r]);

为了做到不重不漏，循环可以先枚举右端点，之后枚举左端点从大到小一直接近0，之后对于每个左右区间，找中间截断点m，之后状态转移即可

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n;
    
    cin>>n;
    
    vector<int> num(n,0);
    
    for(int r = 0;r < n;r++)
    {
        cin>>num[r];
    }
    
    vector<vector<int>> dp(n + 7,vector<int>(n + 7,LLONG_MAX));
    
    vector<vector<int>> sum(n + 7,vector<int>(n + 7,0));
    
    for(int y = 0;y < n;y++)
    {
        for(int u = y;u >= 0;u--)
        {
            sum[u][y] = sum[u + 1][y] + num[u];
        }
    }
    
    for(int r = 0;r < n;r++)
    {
        dp[r][r] = 0;//只是“合并价值”
    }
    
    for(int y = 1;y < n;y++)
    {
        dp[y - 1][y] = num[y - 1] + num[y];
    }
    
    for(int r = 2;r < n;r++)
    {
        for(int l = r - 2;l >= 0;l--)
        {
            for(int m = l;m < r;m++)
            {
                dp[l][r] = min(dp[l][r],dp[l][m] + dp[m + 1][r] + sum[l][r]);
            }
        }
    }
    
    cout<<dp[0][n - 1]<<endl;
    
    return 0;
}