合并石子

题目

在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请设计一个程序，计算出将N堆石子合并成一堆的最小得分。

输入

每组数据第1行为一个正整数N(2<=N<=100)，以下N行，每行一个正整数，小于10000，分别表示第i堆石子的个数(1<=i<=N)。

输出

对于每组数据输出一个正整数，即最小得分

Sample Input

7
13
7
8
16
21
4
18

Sample Output

239

解析

这道题就是一行数，每次将两个石子合并并得到新石子的得分
贪心不能用，整体最优解并不代表部分最优解
所以，我们使用DP，动态规划常用从部分整体最优解的拆分来得到最优解法的递归式，我们可以想到，此处是由2堆石子合并，所以最终最优解肯定是由两个局部最优解加上整体的和求得。
上代码！

代码1

#include<iostream>
#include<cstdio>
using namespace std;
long long n,a[101],b[101][101],s[101];
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)cin>>a[i];
    for(long long i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    for(long long i=n-1;i>=1;i--)//枚举边界
 {
  for(long long j=i+1;j<=n;j++)//枚举长度
  {
            b[i][j]=0x7f7f7f7f;
   for(long long k=i;k<=j-1;k++)b[i][j]=min(b[i][j],b[i][k]+b[k+1][j]+s[j]-s[i-1]);
  }
 }
    cout<<b[1][n];
    return 0;
}

代码2

#include<iostream>
#include<cstdio>
using namespace std;
long long n,a[101],b[101][101],c[101];
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)cin>>a[i];
    for(long long i=1;i<=n;i++)c[i]=c[i-1]+a[i];
    for(long long i=2;i<=n;i++)//枚举长度
 {
  for(long long j=1;j<=n-i+1;j++)//枚举边界
  {
   long long t=j+i-1;
            b[j][t]=0x7f7f7f7f;
   for(long long k=j;k<=t;k++)b[j][t]=min(b[j][t],b[j][k]+b[k+1][t]+c[t]-c[j-1]);
  }
 }
    cout<<b[1][n];
    return 0;
}

代码3

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[101],b[101][101],s[101];//b[i][j]表示从第i个起，接下来j个数合并的最小代价
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    for(int l=1;l<=n;l++)//枚举边界
 {
  for(int i=1;i<=n;i++)//枚举长度
  {
   b[i][l]=0x7f7f7f7f;
   for(int j=1;j<l;j++)b[i][l]=min(b[i][l],b[i+j][l-j]+b[i][j]+s[l+i-1]-s[i-1]);
   if(l==1)b[i][l]=0;
  }
 }
    cout<<b[1][n];
    return 0;
}