标签搜索

目 录CONTENT

文章目录

网易--合唱团.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 6 阅读 / 1,741 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

网易--合唱团

@[toc]

一、题目描述

在这里插入图片描述
在这里插入图片描述

二、分析

  •  这个是算法里面一直比较难的,当我拿到这个题的时候,有点难以下手,虽然知道要用动态规划但是如何用,自己完全不知道,首先想到找出这个n个数中k个最大的相乘,但是很遗憾不对,
  •  题目的细节①要求相邻两个学生之间的编号差不能超过d,②能力值存在负数(吐槽一下,这个能力值为负数就有点恐怖了)
  •  接动态规划的套路
  •  (1)明确状态与选择:状态就是当前已经选中的人数和以谁结尾,选择就是每个man;那么我们需要维护两个数组,因为能力值有负数,负负会得正。
dpm[i][j]表示选中了i个人,以第j个人结尾的能力最大乘积

dpn[i][j]表示选中了i个人,以第j个人结尾的能力最小乘积
  •  (2)状态转移方程:
  • 选中了i-1个人,以j-1结尾,再选中第j个人时
最大乘积为dpm[i][j] = max(dpm[i - 1][j - 1] * num[j],
										dpn[i - 1][j - 1] * num[j]);

最小乘积为dpn[i][j] = min(dpm[i - 1][j - 1] * num[j],
										dpn[i - 1][j - 1] * num[j]);
  • 但由于前i-1个人的最大乘积和最小乘积不一定以第j-1个人结尾,所以我们从允许与j相隔最远的人max(1,j-D)开始遍历直到j-1,不断更新dpm[i][j],dpn[i][j],最后得出的dpm[i][j],dpn[i][j]便是选中i个人,以j结尾的最大、最小乘积。
  •  (3)base case:
dpm[1][j] = dpn[1][j] = num[j];   

dpm[i][1] = dpn[i][1] = num[1];
  •  (4)返回值:
dpm[K][j],dpn[K][j]的最大值

三、代码

#include <bits/stdc++.h>    
using namespace std;    
      
int main()    
{    
      int n;   
      cin>>n;

	  //能力数组
      vector<int> num(n + 1);  
      for(int i = 1; i <= n; i++)    
      {    
          cin>>num[i];    
      }    
      
      //代表选择的人数k和最大间距D
      int K;    
      int D;    
      cin>>K>>D;    
      
      //最大乘积数组
      //dpm[i][j]表示选中了i个人,以第j个人结尾的能力最大乘积    
      vector<vector<long>> dpm(K + 1,vector<long>(n + 1));

	  //最小乘积数组
	  //dpn[i][j]表示选中了i个人,以第j个人结尾的能力最小乘积    
      vector<vector<long>> dpn(K + 1,vector<long>(n + 1));;
      
      //初始化:base case
      for(int j = 1; j < n + 1; j++)    
      {   
          dpm[1][j] = num[j];    
          dpn[1][j] = num[j];    
      }    
	  
	  for(int i = 1; i < K + 1; i++)
      {
          dpm[i][1] = num[1];
          dpn[i][1] = num[1];
      }
  
  	  //第一层循环代表已经选择的人数
      for(int i = 2;i < K + 1;i++)
      {
      	  //第二层循环代表以谁结尾
          for(int j = 2;j < n + 1;j++)
          {
              //第三层循环代表枚举j - D到j - 1中最大的dpm或者最小的dpn
              //因为dpm[j - 1]/dpn[j - 1]并不一定是最大的
              for(int k = max(1,j - D);k < j;k++)
              {
                  dpm[i][j] = max(dpm[i][j],
                  				  max(dpm[i - 1][k] * num[j],
                  				      dpn[i - 1][k] * num[j])
                  			  );
                  			  
                  dpn[i][j] = min(dpn[i][j],
                                  min(dpm[i - 1][k] * num[j],
                                      dpn[i - 1][k] * num[j])
                              );
              }
          }
      }
      
      //循环求结果
      long ret = max(dpm[K][1],dpn[K][1]);
      for(int j = 2;j < n + 1;j++)
      {
          ret = max(max(dpm[K][j],dpn[K][j]),ret);
      }
      cout<<ret<<endl;
      return 0;
  }                      
0

评论区