網易–合唱團

文章目錄

• 網易--合唱團
• • 一、題目描述
  • 二、分析
  • 三、代碼

一、題目描述

二、分析

• 這個是算法里面一直比較難的，當我拿到這個題的時候，有點難以下手，雖然知道要用動態規劃但是如何用，自己完全不知道，首先想到找出這個n個數中k個最大的相乘，但是很遺憾不對，
• 題目的細節①要求相鄰兩個學生之間的編號差不能超過d，②能力值存在負數（吐槽一下，這個能力值為負數就有點恐怖了）。
• 接動態規劃的套路
• （1）明確狀態與選擇：狀態就是當前已經選中的人數和以誰結尾，選擇就是每個man；那么我們需要維護兩個數組，因為能力值有負數，負負會得正。

dpm[i][j]表示選中了i個人，以第j個人結尾的能力最大乘積dpn[i][j]表示選中了i個人，以第j個人結尾的能力最小乘積

• （2）狀態轉移方程：
• 當選中了i-1個人，以j-1結尾，再選中第j個人時：

最大乘積為dpm[i][j] = max(dpm[i - 1][j - 1] * num[j],dpn[i - 1][j - 1] * num[j]);最小乘積為dpn[i][j] = min(dpm[i - 1][j - 1] * num[j],dpn[i - 1][j - 1] * num[j]);

• 但由于前i-1個人的最大乘積和最小乘積不一定以第j-1個人結尾，所以我們從允許與j相隔最遠的人max(1,j-D)開始遍歷直到j-1,不斷更新dpm[i][j]，dpn[i][j],最后得出的dpm[i][j]，dpn[i][j]便是選中i個人，以j結尾的最大、最小乘積。
• （3）base case：

dpm[1][j] = dpn[1][j] = num[j]; dpm[i][1] = dpn[i][1] = num[1];

• （4）返回值：

dpm[K][j],dpn[K][j]的最大值

三、代碼

#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n;//能力數組vector<int> num(n + 1); for(int i = 1; i <= n; i++) { cin>>num[i]; } //代表選擇的人數k和最大間距Dint K; int D; cin>>K>>D; //最大乘積數組//dpm[i][j]表示選中了i個人，以第j個人結尾的能力最大乘積 vector<vector<long>> dpm(K + 1,vector<long>(n + 1));//最小乘積數組//dpn[i][j]表示選中了i個人，以第j個人結尾的能力最小乘積 vector<vector<long>> dpn(K + 1,vector<long>(n + 1));;//初始化:base casefor(int j = 1; j < n + 1; j++) { dpm[1][j] = num[j]; dpn[1][j] = num[j]; } for(int i = 1; i < K + 1; i++){dpm[i][1] = num[1];dpn[i][1] = num[1];}//第一層循環代表已經選擇的人數for(int i = 2;i < K + 1;i++){//第二層循環代表以誰結尾for(int j = 2;j < n + 1;j++){//第三層循環代表枚舉j - D到j - 1中最大的dpm或者最小的dpn//因為dpm[j - 1]/dpn[j - 1]并不一定是最大的for(int k = max(1,j - D);k < j;k++){dpm[i][j] = max(dpm[i][j],max(dpm[i - 1][k] * num[j],dpn[i - 1][k] * num[j]));dpn[i][j] = min(dpn[i][j],min(dpm[i - 1][k] * num[j],dpn[i - 1][k] * num[j]));}}}//循環求結果long ret = max(dpm[K][1],dpn[K][1]);for(int j = 2;j < n + 1;j++){ret = max(max(dpm[K][j],dpn[K][j]),ret);}cout<<ret<<endl;return 0;}

總結

以上是生活随笔為你收集整理的网易--合唱团的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。