题解 | 能量项链

能量项链

https://www.nowcoder.com/practice/565e5812eeab4d8d8449adebcb6583ef

//  #牛客春招刷题训练营# 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;
}

#写题解领奖励##牛客春招刷题训练营#
全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务