dp思路_1255蓝桥杯算法提高-能量项链

dp思路；

dp[i,j]表示从i到j的最大能量；将每一次的合并都简化成两步：

1. 在第k个和k+1之前断开，分别找到i->k和k+1->j的的最大能量dp[i,k], dp[k+1,j]；

2. 再把这两个合并得到dp[i,j]；

所以可以得到动态规划方程dp[i,j] = max(dp[i,j], dp[i,k] + dp[k+1,j] + a[i] * a[k + 1] * a[j + 1])

(a[i] * a[k + 1] * a[j + 1]是最后剩下的两颗珠子合并的能量，注意的是合并之后第k个珠子的尾巴 == 第k+1个的头a[k+1])；

而题目中的要求的是一条项链，所以是一个环，所以没有明确的头和尾，可以从任意的一颗珠子为i开头，任意的j结尾，

解环为链，将长度为n的a数组->a[2n]：将数组a复制一个放到结尾接着，就可以模拟环状的从任意开头->任意结尾；

枚举区间len : i -> j 的长度

参考代码:

#include<iostream>
using namespace std;
int dp[1005][1005];
int a[1005];
int n;
int ans;
int main(){
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		a[i + n] = a[i]; //拆环变链，n->2n 
		dp[i][i] = 0;
	}
	for(int len = 2; len <= n; len++){ //i -> j 的长度
		for(int i = 1; i <= 2 * n; i++){
			int j = i + len - 1; 
			for(int k = i; k < j; k++){
				dp[i][j] = max(dp[i][j],dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]);
			}
		}
	}
	for(int i = 1; i <= n; i++){
		ans = max(ans, dp[i][i + n - 1]);
	}
	cout<<ans;
	return 0;
} //此代码参考本网站咖啡