资源限制 时间限制：2.0s 内存限制：256.0MB 问题描述 在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。 输入格式 输入第一行包含一个整数n，表示石子的堆数。 接下来一行，包含n个整数，按顺序给出每堆石子的大小 。 输出格式 输出一个整数，表示合并的最小花费。 样例输入 5 1 2 3 4 5 样例输出 33 数据规模和约定 1<=n<=1000, 每堆石子至少1颗，最多10000颗。
动态规划，上次国庆前做这道题写了一个晚上也只有91分，这次10分钟就搞定了果然做题这种事还是要看状态。具体思想见代码
#include<stdio.h> #include<algorithm> using namespace std; typedef long long ll; ll dp[1007][1007];//i到j的移动石子的最小数目 ll sum[1007];//前缀和数组 ll arr[1007];//储存石子 ll inf=1000000000000009; int main() { fill(dp[0],dp[0]+1007*1007,inf);//因为是寻找最小移动数所以赋一个较大的值 int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",&arr[i]); sum[i]=sum[i-1]+arr[i]; dp[i][i]=0;//从i到i不需要移动石子 } for(int i=n-1;i>0;i--)//从后往前枚举起点 { for(int j=i+1;j<=n;j++)//枚举终点 { if(j-i==1) { dp[i][j]=arr[i]+arr[j]; continue; } for(int z=i;z<j;z++) { dp[i][j]=min(dp[i][j],dp[i][z]+dp[z+1][j]+sum[j]-sum[i-1]); } } } // for(int i=n-1;i>0;i--) // { // for(int j=i+1;j<=n;j++) // { // // printf("dp[%d][%d]:%lld\n",i,j,dp[i][j]); // } // } printf("%lld",dp[1][n]); return 0; }