NC51170 石子合并

题目描述

设有N堆沙子排成一排，其编号为 。每堆沙子有一定的数量，可以用一个整数来描述，现在要将这 堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有 堆沙子分别为 ，我们可以先合并 堆，代价为 ，得到 ， 又合并 堆，代价为 ，得到 ，再合并得到 ，总代价为 ，如果第二步是先合并 堆，则代价为 ，得到 ，最后一次合并代价为 ，总代价为 。问题是：找出一种合理的方法，使总的代价最小。输出最小代价。

输入描述

第一行一个数 表示沙子的堆数 。
第二行 个数，表示每堆沙子的质量 。

输出描述

合并的最小代价

示例1

输入
4
1 3 5 2
输出
22

分析

经典区间 问题。
定义 为合并区间 的最小代价。则有 （ 为区间 内石子的个数）。相当于将 拆成两个区间 和 ，两个区间各自合并石子需要 和 的代价，将两个区间合并要花费 的代价。
进行递推时，最外层循环为 ，控制右边界；第二层循环从 到 ，控制左边界；第三层循环控制分界点。

代码

#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#define N 302
using namespace std;
int dp[N][N];
int n;
int sum[N];
int a[N];
int main()
{
    memset(dp,0x3f,sizeof(dp));//初始化
    int i,j,k;
    cin>>n;
    for(i=1;i<=n;i++) scanf("%d",a+i);
    //预处理前缀和,O(1)得到count(i,j)
    for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
    //注意循环的顺序
    for(j=1;j<=n;j++)
    {
        //逆序更新，优先更新靠近边界的值
        for(i=j;i>=1;i--)
        {
            if(i==j) dp[i][j]=0;
            for(k=i;k<j;k++)
            {
                dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],dp[i][j]);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}