有 n 個(gè)學(xué)生站成一排，每個(gè)學(xué)生有一個(gè)能力值，牛牛想從這 n 個(gè)學(xué)生中按照順序選取 k 名學(xué)生，要求相鄰兩個(gè)學(xué)生的位置編號的差不超過 d，使得這 k 個(gè)學(xué)生的能力值的乘積最大，你能返回最大的乘積嗎？
輸入描述: 每個(gè)輸入包含 1 個(gè)測試用例。每個(gè)測試數(shù)據(jù)的第一行包含一個(gè)整數(shù) n (1 <= n <= 50)，表示學(xué)生的個(gè)數(shù)，接下來的一行，包含 n 個(gè)整數(shù)，按順序表示每個(gè)學(xué)生的能力值 ai（-50 <= ai <= 50）。接下來的一行包含兩個(gè)整數(shù)，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; }; //聲明結(jié)構(gòu)體，因?yàn)橛姓胸?fù)所以要保存最大值和最小值 //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結(jié)尾的至多包含k個(gè)數(shù)字的成績的最大值和最小值； 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;}新聞熱點(diǎn)
疑難解答
