动态规划合并石子（C++代码）

1731 阅读 1 评论 0 点赞

定义 dp[i][j]：将第i堆到第j堆的所有石子合并的最小花费；
定义 A[i][k]：将第i堆到第k堆的所有石子合并后的石子
定义 sum[i]: 前i堆石子总数

那么 A[i][j]=A[i][k]*A[k+1][j] (k=i to j-1)
在合并A[i][k]和A[k+1][j]的时候，合并的费用为 sum[j] - sum[i - 1];
这样将在k从i遍历到j-1的过程中,更新dp[i][j]的值。

即转态转移方程为：

###### dp[i][j] = min{ dp[i][j] , dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1] }

###### 注意 结果有可能超过int的范围注意
(我的代码写得有点丑）
```cpp
#include <iostream>
#include <stdio.h>
using namespace std;
const long long inf = 9999999999998;
long long dp[1001][1001], sum[1001];
int n, a[1001];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    for (int p = 1; p < n; ++p)
    {
        for (int i = 1; i <= n - p; ++i)
        {
            int j = i + p;
            for (int k = i; k < j; ++k)
            {
                long long q1 = dp[i][j];
                long long q2 = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
                if (!q1)
                    dp[i][j] = q2;
                else
                    dp[i][j] = q1 > q2 ? q2 : q1;
            }
        }
    }
    printf("%lld\n", dp[1][n]);
    system("pause");
    return 0;
}
```

0.0分

6 人评分

本文分类：题解列表
浏览次数：1731 次浏览
发布日期：2020-03-13 18:04:38
本文链接：https://blog.dotcpp.com/a/67891

上一篇 > Manchester-【字符串问题】
下一篇 > 蓝桥杯算法提高VIP-矩阵乘法（C++代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 1 条评论

庞发月 3年前回复TA

为什么我的代码会超时？
#include<iostream>
using namespace std;
const int ma=1000;
int len,f[ma][ma],s[ma];
int main(){
	int temp;
	cin>>len;
	for(int i=1;i<=len;i++){
		cin>>temp;
		s[i]=s[i-1]+temp;
		f[i][i]=0;
	}
	for(int l=2;l<=len;l++){
		for(int i=1;i<=len-l+1;i++){
			int j=i+l-1;
			int minn=0x3f3f3f3f;
			for(int k=i;k<j;k++){
				minn=min(f[i][k]+f[k+1][j]+s[j]-s[i-1],minn);
			}
			f[i][j]=minn;
		}
	}
	cout<<f[1][len];
	return 0;
}
感谢帮助！！

动态规划 合并石子 （C++代码）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 1 条评论

发表评论 取消回复

动态规划合并石子（C++代码）

评论列表共有 1 条评论

发表评论取消回复