1203

用户名：dotcpp0602064

访问量：1908

签　名：

时间是你最大的敌人

等　　级
排　　名	3315
经　　验	1964
参赛次数	0
文章发表	21
年　　龄	19
在职情况	学生
学　　校	中山大学
专　　业	软件工程

　　自我简介：

TA的其他文章

C/C++，高精度模板题（加法、减法、乘法、除法），会套就行~~
浏览：126

C/C++，高精度模板题（加法、减法、乘法、除法），会套就行~~
浏览：44

你可能喜欢

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

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言dp小白一个

　　作者: 1203　　　　发表时间：2022-11-17 18:07:43 浏览：103　|　评论：0　

原题链接：信息学奥赛一本通T1569-石子合并

下面推导一下最大值的情况，最小值同理
![](/image_editor_upload/20221117/20221117063323_80343.png)

int max(int a, int b)
	{
		return a > b ? a : b;
	}
	int min(int a, int b)
	{
		return a < b ? a : b;
	}
	const int INF = 0x3f3f3f3f;
	int n;
	int f[210][410];// 求最大值
	int g[210][410];// 求最小值
	int a[410];// 求前缀和
	int arr[410];// 输入的数据
	int main()
	{
		memset(f, -INF, sizeof f);// 每个值置为 -INF
		memset(g, INF, sizeof g); // 每个值置为 INF
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &arr[i]);
			arr[i + n] = arr[i];// 将链状化为环状
		}
		for (int i = 1; i <= 2 * n; i++)
		{
			a[i] = a[i - 1] + arr[i];
			f[i][i] = 0;
			g[i][i] = 0;
		}
		for (int len = 2; len <= n; len++)// 计算 len 堆石子合并的情况
		{
			for (int l = 1; l + len - 1 < 2 * n; l++)// 起点
			{
				int r = l + len - 1;// 终点
				for (int k = l; k < r; k++)// 决策方法
				{
					f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + a[r] - a[l - 1]);
					g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + a[r] - a[l - 1]);
				}
			}
		}
		int maxx = -INF, minn = INF;
		for (int i = 1; i <= n; i++)
		{
			maxx = max(maxx, f[i][i + n - 1]);// 从 i ~ i + n - 1 有n堆
			minn = min(minn, g[i][i + n - 1]);
		}
		printf("%d\n%d", minn, maxx);
		return 0;
	}
	还可以参考一下本人关于能量项链那道题的题解，应该会有帮助

0.0分

1 人评分

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

1203

TA的其他文章

你可能喜欢

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

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言训练-计算一个整数N的阶乘（C语言代码）

开心的金明（C++代码）

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

C语言dp小白一个

评论区

精彩推荐

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

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

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

Pascal三角（C语言代码）

小O的乘积（C++代码）

马拦过河卒（C语言代码）

陶陶摘苹果2 （C++代码）

1074题初学者，求帮忙看下,不知道哪错了

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

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

1203

TA的其他文章

你可能喜欢

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

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言训练-计算一个整数N的阶乘 （C语言代码）

开心的金明 （C++代码）

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

C语言dp小白一个

评论区

精彩推荐

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

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

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

Pascal三角 （C语言代码）

小O的乘积 （C++代码）

马拦过河卒 （C语言代码）

陶陶摘苹果2 （C++代码）

1074题 初学者，求帮忙看下,不知道哪错了

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

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

C语言训练-计算一个整数N的阶乘（C语言代码）

开心的金明（C++代码）

　　评论区

Pascal三角（C语言代码）

小O的乘积（C++代码）

马拦过河卒（C语言代码）

1074题初学者，求帮忙看下,不知道哪错了

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