题解 | 能量项链

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  我是看的第二篇（下数上）题解才写出来的，虽然这几天写的都是这种len从小到大的dp，但是自己没写出来
#include <iostream>
#include <algorithm>
#include <vector>
#define pi pair<int, int>
#define ll long long
#define beto(x) static_cast< x >
#define pre(i, j, k) for (ll i = j; i < k; i++)
using namespace std;
const int mod = beto(int)(1e9 + 7);
int main(){
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  vector<pi> boxs(2 * n);//---------------手链是循环的可以转动的为了方便处理，复制一份在后面
  {//--------输入并处理boxs
    vector<int> a(n);
    pre(i, 0, n) cin >> a[i];
    pre(i, 0, n - 1) boxs[i].first = a[i], boxs[i].second = a[i + 1];
    boxs[n - 1].first = a[n - 1];
    boxs[n - 1].second = a[0];
    pre(i, 0, n) boxs[i + n] = boxs[i];
  }
  int finans = 0;//--------记录答案
  pre(start, 0, n){
    vector<pi> temp_box(n);
    pre(i, 0, n){//------------以start为起点生成一个手
      temp_box[i] = boxs[i + start];
    }
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));//-----------这里注意初始化为0,dp[i][j]表示在temp_box中索引i~j的珠子都合为一个后所能释放的最大能量
    pre(len, 2, n + 1){//--------------从2开始枚举len因为当len小于2时释放的能量都是0
      pre(i, 0, n){
        int j = i + len - 1;
        if (j >= n) break;//---------防止越界
        if (len == 2){
          dp[i][j] = temp_box[i].first * temp_box[i].second * temp_box[j].second;
        }
        else{
          dp[i][j] = max((beto(ll)(dp[i][j - 1]) + temp_box[i].first * temp_box[j - 1].second * temp_box[j].second) % mod, (beto(ll)(dp[i + 1][j]) + temp_box[i].first * temp_box[i].second * temp_box[j].second) % mod);//---------这里以max中的第一个参数为例，前面i~（j-1）的珠子已经融合为头是temp_box[i].first尾是temp_box[j-1].second的珠子了，在融合最后一个.
          int modmax = 0;
          pre(k, i, j){//---------k是i,j之间的断点,用来模拟更多情况,因为每个len都会进行这个循环所以实际上,相当于设置了很多个断点
            modmax = max(beto(ll)(modmax), beto(ll)(dp[i][k]) + temp_box[i].first * temp_box[k].second * temp_box[j].second + dp[k + 1][j] % mod);
            //dp[i][j] = max(modmax, dp[i][j]);//------------这个删掉好了
          }
          dp[i][j] = max(dp[i][j], modmax);
        }
      }
    }
    finans = max(dp[0][n - 1], finans);
  }
  cout << finans;
  return 0;
}