題目描述

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

輸入描述:

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

輸出描述:

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

示例1

輸入

3
7 4 7
2 50

輸出

49

---

/*
思路：
因為有正有負，負負得正，所以要維護兩個dp數組，一個存儲最大，一個存儲最小。
定義fm[k][i]表示當選中了k個學生，并且以第i個學生為結尾，所產生的最大乘積；
fn[k][i]表示當選中了k個學生，并且以第i個學生為結尾，所產生的最小乘積；
那么fm[k+1][i+1]=max(fm[k][i]*stu[i+1],fn[k][i]*stu[i+1])，
即當選中了k個學生后，再選擇第i+1編號學生，所產生的最大乘積；
然而，并不能保證上一次選擇的就是第i個學生，所以要遍歷子數組fm[k]，
令j從i到1，并且j與i+1之間小于間隔D，遍歷fm[k][j]，以及fn[k][j]；
同理fn[k+1][i+1]=min(fn[k][i]*stu[i+1],fm[k][i]*stu[i+1])。
最后，遍歷一遍fm[K][i]求得最大值（i從1～N）。
*/

#include<iostream> #include <climits> using namespace std; int main(){int N,K,D,i,j,k;long long stu[50],fmax[11][51] = {LONG_LONG_MIN},fmin[11][51] = {LONG_LONG_MAX},res = LONG_LONG_MIN;while(cin >> N){for(i=0;i<N;i++)cin >> stu[i];cin >> K >> D;for(i=1;i<=N;i++){fmax[1][i]=fmin[1][i]=stu[i-1];for(k=2;k<=K;k++){for(j=i-1;j>=k-1 && i-j<=D;j--){// fmax[k][i]和fmin[k][i]需要滿足i>=k.fmax[k][i]=max(fmax[k][i],max(fmax[k-1][j]*stu[i-1],fmin[k-1][j]*stu[i-1]));fmin[k][i]=min(fmin[k][i],min(fmin[k-1][j]*stu[i-1],fmax[k-1][j]*stu[i-1]));}}res=max(res,fmax[K][i]);}cout << res << endl;;}return 0; }

?

總結

以上是生活随笔為你收集整理的有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？的全部內容，希望文章能夠幫你解決所遇到的問題。

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