1203

用户名：dotcpp0602064

访问量：1916

签　名：

时间是你最大的敌人

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

　　自我简介：

TA的其他文章

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

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

你可能喜欢

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

C语言代码，刚了解动态规划，可以看看我的理解，写得很详细

　　作者: 1203　　　　发表时间：2022-11-16 02:13:16 浏览：147　|　评论：0　

原题链接：能量项链

![](/image_editor_upload/20221116/20221116020127_97010.png)
![](/image_editor_upload/20221116/20221116103549_26264.png)

建议耐心读完，应该会有收获

#include<stdio.h>
	int max(int a, int b)// 求最大值
	{
		return a > b ? a : b;// 宏定义也可以 #define max(a,b) ((a)>(b))?(a):(b)
	}
	int dp[210][210];// 用来记录下面dp[i][j]，即表示从第i颗珠子到第j颗珠子可获得的最大能量，包含j-i颗珠子
	
	int a[210];// 用来记录每颗珠子的能量值
	
	int main()
	{
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			a[i + n] = a[i];// 利用复制的方法将环状珠子转变为链状珠子
		}
		for (int len = 2; len <= n; len++)// 这里的len表示有n颗珠子，从2颗珠子开始递推，这里的每一次循环即获得len长度的项链的能量最大值
		{
			for (int l = 1; l + len <= 2 * n; l++)// l即表示最左边
			{
				int r = len + l;// r即表示最右边
				
				for (int k = l + 1; k < r; k++)// k即表示l与r之间
				{
					
					dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);// 即状态转移方程，简单来说就是不同的决策方案，即k的位置不同，所做决策即不同，答案即不同
					不理解a[l] * a[k] * a[r] 可以想一下这个：dp[1][4] = dp[1][2] + dp[2][4] + a[l] * a[k] * a[r], 很明显这里dp[1][2]（或者dp[2][3]）没有意义也就是一颗珠子，定义为全局变量自动初始化为0，也就是算dp[2][4]，那么必然还剩下头尾的2, 4组成一颗珠子，与上面的1，2组成两颗珠子，此时即变为a[l] * a[k] * a[r]，最后即剩下1，4组成一颗珠子
					
					//printf("dp[%d][%d]: %d ",l ,r ,dp[l][r]); 建议打印出来逐步分析一下
				}
			}
		}
		int ret = 0;
		// 求n颗珠子所得到的最大能量
		for (int i = 1; i <= n; i++)
		{
			ret = max(ret, dp[i][i + n]);// dp[i][i+n]即从第i颗珠子到第i+n颗珠子之间的最大能量，之间长度就是n，
		}
		printf("%d", ret);
		return 0;
	}
	ps:第一次写这个，有些地方写得不好，思路基本上这样，小伙伴们可自行理解一下，欢迎大家一起讨论！

0.0分

5 人评分

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

1203

TA的其他文章

你可能喜欢

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

Lucky Word （C++代码）

分糖果（C++代码）

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

钟神赛车（C语言代码）

C语言代码，刚了解动态规划，可以看看我的理解，写得很详细

评论区

精彩推荐

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

C语言训练-列出最简真分数序列* （C语言代码）

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

1124题解

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

字符串输入输出函数（C语言代码）

矩阵的对角线之和（C语言代码）

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

生日日数（C语言代码）

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

1203

TA的其他文章

你可能喜欢

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

Lucky Word （C++代码）

分糖果 （C++代码）

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

钟神赛车 （C语言代码）

C语言代码，刚了解动态规划，可以看看我的理解，写得很详细

评论区

精彩推荐

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

C语言训练-列出最简真分数序列* （C语言代码）

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

1124题解

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

字符串输入输出函数 （C语言代码）

矩阵的对角线之和 （C语言代码）

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

生日日数 （C语言代码）

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

分糖果（C++代码）

钟神赛车（C语言代码）

　　评论区

字符串输入输出函数（C语言代码）

矩阵的对角线之和（C语言代码）

生日日数（C语言代码）