算法背景:
有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子合并为1堆。在合并的过程中只能每次将相邻的两堆石子合并,每次合并的花费为这两堆石子之和,求合并成1堆的最小花费。
dp[i][j]表示将区间[i, j]合并成1堆的最小代价。
#include<bits/stdc++.h> #define MAX 105 #define INF 0x3f3f3f3f using namespace std; int n,dp[MAX][MAX],sum[MAX]; int main() { while(~scanf("%d",&n)) { int i,j,k,x; memset(dp,INF,sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d",&x); sum[i]=sum[i-1]+x; dp[i][i]=0; } for(int len=2;len<=n;len++) { for(i=1;i+len-1<=n;i++) { j=i+len-1; for(k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); } } printf("%d ",dp[1][n]); } return 0; }