【CH 5301】石子归并【DP】

本文主要是介绍【CH 5301】石子归并【DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：http://contest-hunter.org:83/contest/0x50「动态规划」例题/5301 石子合并
每次可以合并连续的两堆石子。代价为这两堆石子的数量之和。求将所有石子合成一堆的最小代价.

---

思路：

这道题不能合并两堆不相邻的石子，所以堆和队列就肯定不行了。考虑DP。
设$f[i][j]$为合并第$i$堆到第$j$堆得最下代价，那么由于肯定得将它们分成两堆来合并，那么就再在$i$和$j$之间枚举个$k$，那么久可以得到方程：
$$f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1])$$
其中$sum$表示前缀和。
最终答案为$f[1][n]$

---

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int n,sum[301],f[301][301];int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&sum[i]);sum[i]+=sum[i-1];  //求前缀和}memset(f,0x3f3f3f3f,sizeof(f));for (int i=n;i>=1;i--){f[i][i]=0;  for (int j=i+1;j<=n;j++) for (int k=i;k<=j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);} printf("%d\n",f[1][n]);return 0;
}

这篇关于【CH 5301】石子归并【DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---