题目大意:
N( 4 ≤ N ≤ 100 ),表示项链上珠子的个数
第二行是N个用空格隔开的正整数,所有的数均不超过1000。
第 i 个数为第 i 颗珠子的头标记( 1 ≤ i ≤ N ),
当 1 ≤ i < N 时,第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。
第N颗珠子的尾标记应该等于第1颗珠子的头标记。
输出是一个正整数E( E ≤ 2.1×109 ),为一个最优聚合顺序所释放的总能量。
Sample Input
4
2 3 5 10
Sample Output
710
一道环形的矩阵连乘
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll n,dp[][],a[];
scanf("%lld",&n);
for(int i=;i<n;i++) scanf("%lld",&a[i]);
for(int i=;i<n;i++) fill(dp[i],dp[i]+,);
for(int i=;i<n;i++) /// 先处理初始状态 最少为相邻两个聚合 即长度为2
dp[i][(i+)%n]=a[i]*a[(i+)%n]*a[(i+)%n];
/// 环形 注意各个位置的求模 i为0~n-1 模n恰好
ll ans=;
for(int i=;i<=n;i++) // 枚举长度 从3开始
for(int l=;l<n;l++) { // 枚举开头
int r=(l+i-)%n; // 得到该长度时的最右端
for(int k=;k<i;k++) { // 枚举分段的长度
int m=(l+k-)%n; // 得到该分段的最右端
dp[l][r]=max(dp[l][r],
dp[l][m]+dp[(m+)%n][r]+a[l]*a[(m+)%n]*a[(r+)%n]);
} /// 左端+右端+左右两端聚合所得能量
if(i==n) ans=max(ans,dp[l][r]); // 更新答案
}
printf("%lld",ans); return ;
}