题目
思路
1.断环成链
2.区间大小枚举
3.区间起点枚举
4.区间的划分枚举
分析
1.可以采用处理环形问题的通用技巧，即复制一份接到后面。这里虽然输入是N个数，但实际上我们要求的是长N + 1的区间的最大能量，所以要将这N个数重复一遍拼在后面，形成长2 N的数组，这样就转化为了线性问题
2.用dp[l][r]来代表区间（l,r）内所有珠子合成的这一颗能量珠所可能释放的最大能量。在区间( l , r )内，能量珠dp[l][r]的头标记为 a[ l ],尾标记为 a[ r+1 ] 用k将区间分成 l~k 和 k+1~r 左右两个部分来代表分左右子珠： dp[l][k]为左子珠所可能产生的最大能量 dp[k+1][r]为右子珠所可能产生的最大能量 k为左子珠的尾标记，k+1为右子珠的头标记
将最初能量珠的数据存到数组w中， 则第 l 颗能量珠的头标记为w[ l ]，尾标记为w[ l + 1 ]，合并珠子即合并左珠dp[l][k]和右珠dp[k+1][r]，释放能量a[l]∗a[k+1]∗a[r+1]
#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll maxn = 1e3 + 5;const ll MOD = 1e9 + 7;const ll INF = 0x7fffffff;ll n;ll w[maxn];ll dp[maxn][maxn];int main() {ios_base::sync_with_stdio(false), cin.tie(0);cin >> n;for (ll i = 1; i <= n; i++) {cin >> w[i];w[i + n] = w[i];}for (ll len = 1; len < n; len++) {for (ll l = 1; l + len <= 2 * n; l++) {ll r = l + len ;for (ll k = l; k < r; k++) {dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + w[l] * w[k + 1] * w[r + 1]);}}}ll res = 0;for (ll i = 1; i <= n; i++) res = max(res, dp[i][i + n-1]);cout << res;return 0;}
