【Tyvj1055】沙子合并

2014-03-29
竞赛题解 / 动态规划
TYVJ

描述 Description

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

输入格式 InputFormat

第一行一个数 N 表示沙子的堆数 N。
第二行 N 个数，表示每堆沙子的质量。n<=1000。

输出格式 OutputFormat

合并的最小代价

样例输入 SampleInput

4
1 3 5 2

样例输出 SampleOutput

22

Tyvj 1055

代码 Code

简单的区间动规。觉得程序不够快的可以试试四边形不等式优化。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x7fffffff
int a[301],sum[301];
int f[500][500];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
    memset(sum,0,sizeof(sum));
    scanf("%d",&n);
    for (i=0;i<n;i++) for (j=0;j<n;j++) f[i][j]=inf;
    for (i=0;i<n;i++) 
    {
        scanf("%d",&a[i]);
        f[i][i]=0;
        sum[i]=(i>0)?sum[i-1]+a[i]:a[i];
    }
    for (i=n-1;i>=0;i--) for (j=i+1;j<n;j++) 
    {
        for (k=i;k<j;k++)
        {
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        }
        f[i][j]+=(i>0)?sum[j]-sum[i-1]:sum[j];
    }
    printf("%d\n",f[0][n-1]);
    return 0;
}