题解 | #合唱团#

#include <iostream>
#include <limits.h>
using namespace std;

int main()
{
 int n,k,d;
 int V[51];
 long long results_max[51][11] = {0};
 long long results_min[51][11] = {0};
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       cin>>V[i]; 
       results_max[i][1] = V[i];
       results_min[i][1] = V[i]; 
    }
    cin>>k>>d;
    for(int i=2;i<=k;i++)
    {
        for(int j=1;j<=n;j++)
        {

            for(int m=max(j-d,1);m<j;m++)
            {
                results_max[j][i] = max(max(results_max[m][i-1]*V[j],results_min[m][i-1]*V[j]),results_max[j][i]);
                results_min[j][i] = min(min(results_max[m][i-1]*V[j],results_min[m][i-1]*V[j]),results_min[j][i]);    
            }

        }
    }
    long long max_res = INT_MIN;
    for(int i=1;i<=n;i++)
    {
      if(results_max[i][k]>max_res){max_res=results_max[i][k];}  
    }
    cout<<max_res<<endl;
 return 0;   
}

本题目是一道典型的“动态规划”问题，什么是动态规划问题呢？我的理解是，对于最终我们所要求取的结果，我们通过求取中间过渡态时的结果，逐步去逼近我们最终想要的结果。最经典的问题当属于求最大面积的问题了。在本问题当中，我们要连续求k个同学的乘积最大值，我们首先分析是否存在过渡态呢？前k-1个同学的所得结果应当是在第k个同学之前，k-1个同学的乘积最大值。因此，我们可以从1开始逐渐去寻找各个同学作为最后一个同学时的乘积最大值，当然因为含有负值，我们还需要考虑最小值。这样的存储结构是最难想到的，我们可以选择一个尽量容量比较大的存储结构，多存储一些情况，基本上二维的存储结构就差不多了。另外，由于涉及到乘积，而且是多达几十次的乘积，我们需要使用long long的数据类型。