合唱團(tuán) 時間限制：1秒?空間限制：32768K?熱度指數(shù)：38059 本題知識點：?動態(tài)規(guī)劃

題目描述

有 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
思路：
fm[i][j]表示已經(jīng)選了i個最后一個為j的最大值。
fn[i][j]表示已經(jīng)選了i個最后一個為j的最小值。
動歸求解。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 51 using namespace std; int n,k,d; int val[MAXN]; long long ans=-0x7f7f7f7f; long long fm[MAXN][MAXN],fn[MAXN][MAXN]; int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&val[i]);fm[1][i]=val[i];fn[1][i]=val[i];}scanf("%d%d",&k,&d);for(int j=1;j<=n;j++){for(int i=2;i<=k;i++)for(int m=j-1;m>=max(i-1,j-d);m--){fm[i][j]=max(fm[i][j],max(fm[i-1][m]*val[j],fn[i-1][m]*val[j]));fn[i][j]=min(fn[i][j],min(fn[i-1][m]*val[j],fm[i-1][m]*val[j]));}ans=max(ans,fm[k][j]);}cout<<ans; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/cangT-Tlan/p/7670016.html

總結(jié)

以上是生活随笔為你收集整理的2017网易校招真题 合唱团的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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