合唱团---DP

https://www.nowcoder.com/practice/661c49118ca241909add3a11c96408c8?tpId=85&tqId=29830&tPage=1&rp=1&ru=/ta/2017test&qru=/ta/2017test/question-ranking

题目描述

有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？

输入描述:

每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 a

_i

（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:

输出一行表示最大的乘积。

示例1

输入

复制

3
7 4 7
2 50

输出

复制

49



注意：此题int型会超出范围，要用 long long 

#include<iostream>
#include<stdio.h>
#include<string.h>
#define ll long long
using namespace std;
ll a[55];//学生能力值存储数列
ll mx[55][11],mn[55][11];//动态数组设为以第i个学生结尾的选取j个人的情况。 
int main()
{
  int n,k,d;
  cin>>n;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  cin>>k>>d;
  for(int i=0;i<n;i++)//初始化
  {
    mx[i][0]=mn[i][0]=a[i];
  }
  for(int i=0;i<n;i++)
  {
    for(int j=1;j<k;j++)
    {
      for(int m=i-1;m>=max(0,i-d);m--)//因为相邻位置编号差不超过d,所以i-(i-1)<=d,---->i-1>=i-d;
      {
        mx[i][j]=max(mx[i][j],max(mx[m][j-1]*a[i],mn[m][j-1]*a[i]));
        mn[i][j]=min(mn[i][j],min(mx[m][j-1]*a[i],mn[m][j-1]*a[i]));//因为能力值有负值，所以负数最小也要考虑
      }
    }
  }
  ll ans=mx[0][k-1];
  for(int i=0;i<n;i++)
  {
    ans=max(ans,mx[i][k-1]);
  }
  cout<<ans<<endl;
  return 0;
}