前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >牛客网 合唱团

牛客网 合唱团

作者头像
发布2018-09-04 11:40:35
6360
发布2018-09-04 11:40:35
举报
文章被收录于专栏:WD学习记录

题目描述

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

输入描述:

代码语言:javascript
复制
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数,k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:

代码语言:javascript
复制
输出一行表示最大的乘积。

示例1

输入

代码语言:javascript
复制
3
7 4 7
2 50

输出

代码语言:javascript
复制
49

1. 题目分析

题目要求n各学生中选择k个,使这k个学生的能力值乘积最大。这是一个最优化的问题。另外,在优化过程中,提出了相邻两个学生的位置编号差不超过d的约束。 如果不用递归或者动态规划,问题很难入手,并且,限制条件d也需要对每一个进行约束,编程十分复杂 所以,解决的方法是采用动态规划(理由:1.求解的是最优化问题;2.可以分解为最优子结构) 2. 问题分解

  • 对该问题的分解是关键

    从n个学生中,选择k个,可以看成是:先从n个学生里选择最后1个,然后在剩下的里选择k-1个,并且让这1个和前k-1个满足约束条件

  • 数学描述

    为了能够编程实现,需要归纳出其递推公式,而在写递推公式之前,首先又需要对其进行数学描述     记第k个人的位置为one,则可以用f[one][k]表示从n个人中选择k个的方案。然后,它的子问题,需要从one前面的left个人里面,选择k-1个,这里left表示k-1个人中最后一个(即第k-1个)人的位置,因此,子问题可以表示成f[left][k-1].     (1)学生能力数组记为arr[n+1],第i个学生的能力值为arr[i]     (2)one表示最后一个人,其取值范围为[1,n];     (3)left表示第k-1个人所处的位置,需要和第k个人的位置差不超过d,因此max{k-1,one-d}<=left<=one-1

    在n和k定了之后,需要求解出n个学生选择k个能力值乘积的最大值。因为能力值有正有负,所以有:

    如上图所示:     当one对应的学生能力值为正时,         f[one][k] = max{f[left][k-1] * arr[i]}        (min{k-1,one-d}<=left<=one-1);     当one对应的学生能力值为负时         f[one][k] = max{g[left][k-1] * arr[i]}       (min{k-1,one-d}<=left<=one-1);     此处g[][]是存储n个选k个能力值乘积的最小值数组

3. 编程实现

    归纳以上思想,我们现在编程实现,可以先根据变量习惯进行变更,得到相应的递推公式。我们从curK = 1递推到curK = K


解答:

代码语言:javascript
复制
N=int(input())
abilties=[int(each) for each in input().split()]
k,d=[int (each) for each in input().split()]
dp=[(each,each) for each in abilties]
for i in range(1,k):
    dp_=dp[:i]
    for j in range(i,N):
        templist=[]
        z_range_min=0
        if j-d>0:
            z_range_min=j-d
        for z in range(z_range_min,j):
            templist.append(abilties[j]*dp[z][0])
            templist.append(abilties[j]*dp[z][1])
        dp_.append((max(templist),min(templist)))
    dp=dp_
print(max([max(each) for each in dp]))

参考:

  1. 合唱团
  2. 《合唱团》算法解析(含思路解答示意图)【牛客网编程题——JAVA实现】
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年08月21日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 输入描述:
  • 输出描述:
  • 输入
  • 输出
  • 解答:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档