问题描述:
有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,你能返回最大的乘积吗?
dpi表示 依次选好第i个学生时 他在队伍里排第j名能力值乘积最大为多少 应该是i>=j
dpi = arr[i] * max(dpi-1);
边界条件 dp0=1;
但是因为每个学生的能力有正有负,所以如果arr[i]为负值,那么dpi = arr[i] * min(dpi-1);
我们可以
用dp1i表示依次选好第i个学生时 他在队伍里排第j名能力值乘积最大为多少
用dp2i表示依次选好第i个学生时 他在队伍里排第j名能力值乘积最小为多少
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long int
const ll maxn = 55;
ll arr[maxn];
ll dp1[maxn][maxn]; //存最大值
ll dp2[maxn][maxn]; //存最小值
int main()
{
ll n; //n个学生
while(cin>>n)
{
for(ll i=1;i<=n;++i)
{
cin>>arr[i]; //每个学生的能力值有正有负
}
ll k,d; //k个学生,编号差值不超过d
cin>>k>>d;
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
for(ll i=0;i<=n;++i)
{
dp1[0][i]=1;
dp2[0][i]=1;
}
for(ll i=1;i<=k;++i)
{
for(ll j=1;j<=n;++j)
{
if(i>j) continue; //选好了I个人,他不可能在原来的队伍
ll num1 = -1<<30;
ll num2 = 1<<30;
for(int m=1;m<=d;++m)
{
if(j-m<0) break;
num1=max(num1,dp1[i-1][j-m]);
num2=min(num2,dp2[i-1][j-m]);
}
dp1[i][j] =max(num2 * arr[j], num1 * arr[j]);
dp2[i][j] =min(num2 * arr[j], num1 * arr[j]);
}
}
ll ans = -1<<30;
// for(int i=0;i<=k;++i)
// {
// for(int j=1;j<=n;++j)
// {
// cout<<dp1[i][j]<<" ";
// }
// cout<<endl;
// }
for(ll i=k;i<=n;++i)
{
ans = max(ans,dp1[k][i]);
}
cout<<ans<<endl;
}
return 0;
}