思路
区间dp，对于我这个弱鸡来说是第一次做啊。。。好神奇QwQ
设dp[i][j]表示左端点为i号珠子，右端点为j号珠子的区间所能得到的最大能量
在读入的时候现将珠子们复制一遍放到后面，断环成链
伪代码
for i : 2 ---> (2*n) //枚举右端点，注意是右端点
for j : (i-n) ---> (i-1) j>=1 //枚举左端点，同时保证区间长度小于等于n
for k : i ---> j //枚举区间断点
dp[j][i] = max(dp[j][i], dp[j][k]+dp[k+1][i]+a[j]*a[k+1]*a[i+1])
这个转移方程应该不难看懂
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[202][202], n, a[202], ans;
int main() {
scanf("%d", &n);
for(int i=1; i<=n; i++) {
scanf("%d", &a[i]);
a[i+n] = a[i];
}
for(int i=2; i<2*n; i++) {
for(int j=i-1; i-j<n&&j>=1; j--) {
for(int k=j; k<i; k++) {
dp[j][i] = max(dp[j][i], dp[j][k]+dp[k+1][i]+a[j]*a[k+1]*a[i+1]);
}
ans = max(ans, dp[j][i]);
}
}
printf("%d", ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9332342.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
