题解 | 能量项链-NOIP2006提高组复赛A题

首先，我们对问题先进行简化，我们没有必要把这个珠子看作是头是多少尾是多少的东西，我们就把它看做一个数，比如2 3 5 10我们就把它看做2 3 5 10当吸收珠子的时候就把一个数字删掉，比如吸收2，那我们就把3拿掉，放出235的能量，若只剩下两个比如2,5 那么我们吸收5就可以看做一个循环释放能量，即252这样就能把数据结构简化很多，后面的思路也会清晰起来。

对于这道题目，珠子与珠子之间的关系非常复杂，而且当吸收完一颗珠子之后，接下来就是一个n-1的项链，也是解这条项链的问题，因此很明显这是一个dp问题。对于n个珠子的项链我们不需要知道其是怎么合成的，只要知道最大值即可。

对于一般的n颗珠子，我们求它的最大能量值。我们可以把它的上一步的时候的组成分为dp[1]max,dp[n-1]max; dp[2]max,dp[n-2]max; dp[3]max,dp[n-3]max ……dp[n]max,dp[1]max;它右这n种情况的合并而成我们只要求出这n种情况的最大值即可求出n颗珠子时的能量的最大值。但是别忘了，题目是没有说起点在哪里的，也没有说方向是向哪里的，因此我们还得以每一个点为起点做一次分组算一遍。

下面就是实现的代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int dp[210][210];
int que[210];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&que[i]);
		que[i+n]=que[i];
	}
	que[0]=que[n];
	for(int j=1;j<2*n;j++){
		for(int i=j;i>=1&&i>j-n;i--){
			for(int k=i;k<j;k++){
				dp[i][j]=max(que[i]*que[k+1]*que[j+1]+dp[i][k]+dp[k+1][j],dp[i][j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i][i+n-1]);
	}
	cout<<ans;
	return 0;
}