115200

用户名：472121315

访问量：5806

签　名：

等　　级
排　　名	1238
经　　验	3062
参赛次数	0
文章发表	18
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

C语言考试练习题_排列-题解(Java代码)
浏览：154

字符排列问题-题解(Java代码)
浏览：153

蓝桥杯算法训练VIP-求先序排列-题解(Java代码)
浏览：241

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

蓝桥杯算法提高-能量项链（Java代码）

　　作者: 115200　　　　发表时间：2020-02-07 18:54:57 浏览：322　|　评论：0　

原题链接：蓝桥杯算法提高-能量项链

环形区间dp
将环形变为线形 1 2 3 4..N 1 2 3..N-1
珠子i的头尾标记分别为b[i][0] b[i][1]
状态转移方程dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]+b[i][0]\*b[k+1][0]\*b[j][1])
代码如下:
```java
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] a = new int [2*N];
		int[][] dp = new int [2*N][2*N];
		for (int i = 0; i < dp.length; i++) {
			Arrays.fill(dp[i], Integer.MIN_VALUE);
			dp[i][i]=0;
		}
		for (int i = 1; i <= N; i++) {
			a[i] = scan.nextInt();
		}
		for (int i = 1; i < N; i++) {
			a[N+i] = a[i];
		}
		int[][] b = new int[2*N][2];
		for (int i = 1; i < 2*N-1; i++) {
				b[i][0] = a[i];
				b[i][1] = a[i+1];
		}
		b[2*N-1][0] = a[2*N-1];b[2*N-1][1] = a[N];
		for (int len = 2; len <=N; len++) {
			for (int i = 1; i+len-1 <=2*N-1; i++) {
				int j = i+len-1;
				for (int k = i; k < j; k++) {
					dp[i][j] = Math.max(dp[i][j], dp[i][k]+dp[k+1][j]+b[i][0]*b[k+1][0]*b[j][1]);
				}
			}
		}
		int ans = 0;
		for (int i = 1; i<=N; i++) {
			if(dp[i][i+N-1]>ans) {
				ans = dp[i][i+N-1];
			}
		}
		System.out.println(ans);
		scan.close();
	}
}
```

0.0分

2 人评分

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

115200

TA的其他文章

你可能喜欢

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

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

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

C语言训练-计算1~N之间所有奇数之和（C语言代码）

字符串的输入输出处理（C语言代码）

蓝桥杯算法提高-能量项链（Java代码）

评论区

精彩推荐

简单的a+b （C语言代码）

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

wu-淘淘的名单（C++代码）

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

printf基础练习2 （C语言代码）

1025题解

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

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

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

计算质因子（Java代码）

115200

TA的其他文章

你可能喜欢

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

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

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

字符串的输入输出处理 （C语言代码）

蓝桥杯算法提高-能量项链 （Java代码）

评论区

精彩推荐

简单的a+b （C语言代码）

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

wu-淘淘的名单 （C++代码）

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

printf基础练习2 （C语言代码）

1025题解

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

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

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

计算质因子 （Java代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

字符串的输入输出处理（C语言代码）

蓝桥杯算法提高-能量项链（Java代码）

　　评论区

wu-淘淘的名单（C++代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

计算质因子（Java代码）