石子合并（区间dp典型例题）

Description

有n堆石子排成一行，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。

Input

第一行一个整数n(1 <= n <= 200)，表示石子堆数；第二行n个整数a(1 <= a <= 100)，表示每堆石子的个数。

Output

一个整数，表示最小总得分。

Sample Input

5

7 6 5 7 100

Sample Output

Source

Unknown

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<map>

#include<cmath>

#define Inf 0x3f3f3f3f

const int maxn=1e5+;

typedef long long ll;

using namespace std;

int a[],g[][],sum[];

int dp[][];

int main()

{

   int n;

   cin>>n;

   for(int t=;t<=n;t++)

   {

       scanf("%d",&a[t]);

   }

   for(int t=;t<=n;t++)

   {

       sum[t]=sum[t-]+a[t];

   }

   memset(dp,Inf,sizeof(dp));

   for(int t=;t<=n;t++)

   {

       for(int j=t;j<=n;j++)

       {

           g[t][j]=sum[j]-sum[t-];

    }

   }

   for(int t=;t<=n;t++)

   {

       dp[t][t]=;

   }

   for(int l=;l<n;l++)

   {

       for(int j=;j+l<=n;j++)

       {

           int r=j+l;

           for(int k=j;k<r;k++)

           {

               dp[j][r]=min(dp[j][r],dp[j][k]+dp[k+][r]+g[j][k]+g[k+][r]);

        }

    }

   }

   cout<<dp[][n]<<endl;

   return ;

}

巴特西

石子合并（区间dp典型例题）

Description

Input

Output

Sample Input

Sample Output

Source

最新文章

热门文章