石子合并

  石子合并
 
问题描述
  在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
输入格式
  输入第一行包含一个整数n,表示石子的堆数。
  接下来一行,包含n个整数,按顺序给出每堆石子的大小 。
输出格式
  输出一个整数,表示合并的最小花费。
样例输入
5
1 2 3 4 5
样例输出
33
数据规模和约定
  1<=n<=1000,每堆石子至少1颗,最多10000颗。
 
分析:区间DP的模板题
dp[i][j]表示第i堆到第j堆的方案
 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
自己需要注意的问题:状态转移方程后面的每个值都要先被赋值
要注意赋值的顺序
 
代码如下
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
int c[1100];
int dp[1100][1100];
int sum[1100]={0}; 
int main()
{
  int n,j;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
  cin>>c[i];
   sum[i]=sum[i-1]+c[i];
  }
  for(int L=1;L<=n-1;L++)
  {
      for(int i=1;i<=n-L;i++)
      {
          
        j=i+L;
        dp[i][j]=INF;
      for(int k=i;k<j;k++)
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);    
    }
  }
  cout<<dp[1][n]<<endl;
  return 0;
} 
原文地址:https://www.cnblogs.com/a249189046/p/6670195.html