22软工孟姿好

用户名：dotcpp0669285

访问量：680

签　名：

莫道桑榆晚，为霞尚满天

等　　级
排　　名	1010
经　　验	3342
参赛次数	12
文章发表	43
年　　龄	20
在职情况	学生
学　　校	bilibili大学
专　　业	软件工程

　　自我简介：

自强不息

TA的其他文章

旧物有情 # 枚举法求素数
浏览：20

旧物有情 # 枚举法求水仙花数
浏览：13

旧物有情 # 遍历求二维数组转置
浏览：8

你可能喜欢

区间dp+前缀和 #1898: 蓝桥杯算法提高VIP-合并石子(C++)

　　作者: 22软工孟姿好　　　　发表时间：2024-11-24 19:37:50 浏览：1　|　评论：0　

原题链接：蓝桥杯算法提高VIP-合并石子

n堆石子,挑选任意一端区间 [L,R]

我们用F[L,R]表示从L到R合并为一堆所需要的**最小代价**

枚举一个切分点,把区间分割为[L,K] - [K+1,R],

那么问题就转为合并 L->K,K+1->R这两堆石子的代价

这其中我们还可以用前缀和数组来快速求 合并[L,R]石子需要的代价

最优解可能存在于某个切分点,我们枚举所有的可能情况

状态计算为 `f[l,r] = min(f[l,r],f[l][k]+f[k+1][r] + s[r]-s[l-1]`
```
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define MAX 0x3f3f3f3f
#define MIN -0x3f3f3f3f
using namespace std;
typedef long long ll;

//该死的题又不说数据范围
const int N = 1010;

int f[N][N], a[N], s[N];

int n;

int main() {
	cin >> n;

//Min运算要给值全部赋值为最大,防止干扰运算
	memset(f, MAX, sizeof f);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		//前缀和数组
		s[i] = s[i - 1] + a[i];
		//合并一堆石子代价为0
		f[i][i] = 0;
	}

//区间长度
	for (int len = 2; len <= n; len++) {
		//区间的左右起点
		//比如说长度为2,n=4,有[1,2] [2,3] [3,4] 三种情况
		for (int l = 1; l + len - 1 <= n; l++) {
			//区间右端点
			int r = l + len - 1;
			for (int k = l; k < r; k++) {
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
			}
		}
	}

cout << f[1][n];

return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

22软工孟姿好

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【明明的随机数】（C语言代码）

台球碰撞（C++代码）

求圆的面积（C++代码）这里推荐使用宏定义

区间dp+前缀和 #1898: 蓝桥杯算法提高VIP-合并石子(C++)

评论区

精彩推荐

【蟠桃记】（C语言代码）

C语言训练-求函数值（C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C语言训练-求素数问题（C语言代码）

WU-判定字符位置（C++代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

星期判断机（C语言代码）

C二级辅导-同因查找（C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

22软工孟姿好

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【明明的随机数】 （C语言代码）

台球碰撞 （C++代码）

求圆的面积 （C++代码）这里推荐使用宏定义

区间dp+前缀和 #1898: 蓝桥杯算法提高VIP-合并石子(C++)

评论区

精彩推荐

【蟠桃记】 （C语言代码）

C语言训练-求函数值 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C语言训练-求素数问题 （C语言代码）

WU-判定字符位置 （C++代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

星期判断机 （C语言代码）

C二级辅导-同因查找 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

【明明的随机数】（C语言代码）

台球碰撞（C++代码）

求圆的面积（C++代码）这里推荐使用宏定义

　　评论区

【蟠桃记】（C语言代码）

C语言训练-求函数值（C语言代码）

C语言训练-求素数问题（C语言代码）

WU-判定字符位置（C++代码）

星期判断机（C语言代码）

C二级辅导-同因查找（C语言代码）