首页 > 代码库 > 合并石子 区间dp水题
合并石子 区间dp水题
合并石子
链接： nyoj 737
- 描述: 有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
- tags：最基本的区间dp，这题范围小，如果n大一些，还是要加个平行四边行优化。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#include<string>using namespace std;typedef long long ll;#define rep(i,a,b) for(int i=a; i<=b; ++i)#define inf 1e18const int N=1005;int n, a[N];ll dp[N][N], f[N][N], sum[N][N], sum1[N];int main(){ while(scanf("%d", &n)!=EOF) { rep(i,1,N-1) rep(j,i,N-1) dp[i][j]=inf; rep(i,1,n) scanf("%d", &a[i]), sum1[i]=sum1[i-1]+a[i]; rep(i,1,n) rep(j,i+1,n) { sum[i][j]=sum1[j]-sum1[i-1]; } rep(i,1,n) f[i][i]=i, dp[i][i]=0; rep(len, 2, n) for(int i=1; i+len-1<=n; ++i) { int j=i+len-1; for(int k=f[i][j-1]; k<=f[i+1][j]; ++k) { if(dp[i][j]>dp[i][k]+dp[k+1][j]+sum[i][j]) { dp[i][j]= dp[i][k]+dp[k+1][j]+sum[i][j]; f[i][j]=k; } } } printf("%lld\n", dp[1][n]); } return 0;}
合并石子 区间dp水题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。