国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

網易編程題(合唱團)

2019-11-10 20:24:26
字體:
來源:轉載
供稿:網友

網易編程題(合唱團)

有 n 個學生站成一排,每個學生有一個能力值,牛牛想從這 n 個學生中按照順序選取 k 名學生,要求相鄰兩個學生的位置編號的差不超過 d,使得這 k 個學生的能力值的乘積最大,你能返回最大的乘積嗎?

輸入描述: 每個輸入包含 1 個測試用例。每個測試數據的第一行包含一個整數 n (1 <= n <= 50),表示學生的個數,接下來的一行,包含 n 個整數,按順序表示每個學生的能力值 ai(-50 <= ai <= 50)。接下來的一行包含兩個整數,k 和 d (1 <= k <= 10, 1 <= d <= 50)。

輸出描述: 輸出一行表示最大的乘積。

輸入例子: 3 7 4 7 2 50

輸出例子: 49

#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){ long long temp_k = -1e17; vector< long long > students; long long n; cin >> n; long long sum = n; while (n--) { long long temp; cin >> temp; students.push_back(temp); } long long k, d; cin >> k >> d; struct min_max{ min_max() :min{ 0 }, max{ 0 }{}; long long min; long long max; }; //聲明結構體,因為有正有負所以要保存最大值和最小值 //vector<vector< long long >> *res = new vector<vector< long long >>{ n, vector< long long >{d, 0} }; vector<vector<min_max>> *res = new vector<vector< min_max>>(sum, vector<min_max>(k, min_max())); for (long long i = 0; i <sum; ++i) { (*res)[i][0].max = (*res)[i][0].min = students[i]; } //以i結尾的至多包含k個數字的成績的最大值和最小值; for (long long i = 1; i <sum; ++i) { for (long long j = 1; j <= i&&j < k; ++j) { long long temp_min = -1e17; long long temp_max = 1e17; for (long long w = 1; w<i + 1 && w <= d; ++w){ if (temp_min<max(students[i] * (*res)[i - w][j - 1].min, students[i] * (*res)[i - w][j - 1].max)) temp_min = max(students[i] * (*res)[i - w][j - 1].min, students[i] * (*res)[i - w][j - 1].max); if (temp_max>min(students[i] * (*res)[i - w][j - 1].min, students[i] * (*res)[i - w][j - 1].max)) temp_max = min(students[i] * (*res)[i - w][j - 1].min, students[i] * (*res)[i - w][j - 1].max); } (*res)[i][j].max = temp_min; (*res)[i][j].min = temp_max; } } for (auto c : (*res)) { if (c[k - 1].max>temp_k) temp_k = c[k - 1].max; } cout << temp_k << endl; delete res; return 0;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 海兴县| 大洼县| 含山县| 沙雅县| 丰原市| 台江县| 嘉定区| 秦皇岛市| 福海县| 沅陵县| 商洛市| 昌图县| 广东省| 加查县| 古交市| 汉沽区| 中西区| 鹿邑县| 梁平县| 福鼎市| 绥滨县| 灵台县| 井冈山市| 南漳县| 鄯善县| 南汇区| 庆安县| 封开县| 桂东县| 浪卡子县| 章丘市| 深州市| 桃园市| 大兴区| 新源县| 南安市| 宜良县| 密云县| 民勤县| 含山县| 浑源县|