一天十題選擇，一天一道編程，一天一個面試題，一個一個劍指offer

排序是必須要掌握的一個算法，非常的重要

題目描述

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

輸入描述:

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

輸出描述:

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

示例1

輸入

3
7 4 7
2 50

輸出

49

題目分析

本題是網(wǎng)易的一道動態(tài)規(guī)劃的題目，題目中讓我們求解的是一個最優(yōu)解的問題，我們這里可以考慮使用的算法是動態(tài)規(guī)劃來進(jìn)行求解，這里我們需要求解從n個人當(dāng)中選擇k使得這k的乘積最大，這個問題我們就需要設(shè)置的 二維數(shù)組，數(shù)組的中表示的是第i個數(shù)作第j個乘數(shù)的時候的最大值，這里我們需要維護(hù)一個最大值的數(shù)組，還需要維護(hù)一個最小值的數(shù)組，原因是，我們的最大值可能是由我們的最小值的一個負(fù)數(shù)乘以一個負(fù)數(shù)得到的，同時我們的最小值也可能是最大值中的一個最大數(shù)乘以我們的一個負(fù)數(shù)得到的，所以這里需要維護(hù)兩個數(shù)組，同時還應(yīng)該注意的一個問題就是，我們的數(shù)據(jù)中，還需要控制的一個間距。

代碼

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int main()
{int n;while (cin >> n){vector<long long> arr(n);for (int i = 0; i<n; i++){cin >> arr[i];}int k, d;cin >> k >> d;vector<vector<long long>> dp_max(n, vector<long long>(k + 1, 0));vector<vector<long long>> dp_min(n, vector<long long>(k + 1, 0));//初始化最大和最小數(shù)組for (int i = 0; i<n; i++){dp_max[i][1] = arr[i];dp_min[i][1] = arr[i];}for (int i = 0; i<n; i++){for (int j = 2; j<k + 1; j++){for (int m = max(0, i - d); m<=i - 1; m++) //這里的m控制的是間隔，就是說，我們的間隔要控制好了{dp_max[i][j] = max(dp_max[i][j], max(dp_max[m][j - 1] * arr[i], dp_min[m][j - 1] * arr[i]));dp_min[i][j] = min(dp_min[i][j], min(dp_min[m][j - 1] * arr[i], dp_max[m][j - 1] * arr[i]));}}}long long maxnum = dp_max[k-1][k];for (int i = k; i<n; i++){maxnum = max(maxnum, dp_max[i][k]);}cout << maxnum << endl;}return 0;
}

總結(jié)

以上是生活随笔為你收集整理的每日一题 -- 11-1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。