题目链接：http://codevs.cn/problem/1048/
题目描述 Description
有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。
问安排怎样的合并顺序，能够使得总合并代价达到最小。
Input Description
第一行一个整数n（n<=100）
第二行n个整数w1,w2...wn (wi <= 100)
Output Description
一个整数表示最小合并代价
Sample Input
4
4 1 1 4
Sample Output
18
思路：简单石子合并。模板题。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=1e2+;
const int INF=0x3f3f3f3f; int dp[maxn][maxn];
int a[maxn],sum[maxn]; int main()
{
int n;
while(scanf("%d",&n)==)
{
sum[]=;
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-]+a[i];
}
memset(dp,,sizeof(dp)); for(int d=; d<n; d++)
{
for(int i=; i+d<=n; i++)
{
int j=i+d;
dp[i][j]=INF;
for(int k=i; k<j; k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]+sum[j]-sum[i-]); }
}
printf("%d\n",dp[][n]);
}
return ;
}
平行四边形优化的石子合并：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=1e2+;
const int INF=0x3f3f3f3f; int dp[maxn][maxn];
int s[maxn][maxn];
int a[maxn],sum[maxn]; int main()
{
//freopen("in.txt","r",stdin);
int n;
while(scanf("%d",&n)==)
{
sum[]=;
memset(s,,sizeof(s));
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
s[i][i]=i;
sum[i]=sum[i-]+a[i];
}
memset(dp,,sizeof(dp)); for(int d=; d<n; d++)
{
for(int i=; i+d<=n; i++)
{
int j=i+d;
dp[i][j]=INF;
for(int k=s[i][j-]; k<=s[i+][j]; k++)
{
if(dp[i][j]>dp[i][k]+dp[k+][j]+sum[j]-sum[i-])
{
dp[i][j]=dp[i][k]+dp[k+][j]+sum[j]-sum[i-];
s[i][j]=k;
}
}
}
}
printf("%d\n",dp[][n]);
}
return ;
}