合唱团---DP
2024-09-03 19:22:37
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
输出
49 注意:此题int型会超出范围,要用 long long
#include<iostream>
#include<stdio.h>
#include<string.h>
#define ll long long
using namespace std;
ll a[];//学生能力值存储数列
ll mx[][],mn[][];//动态数组设为以第i个学生结尾的选取j个人的情况。
int main()
{
int n,k,d;
cin>>n;
for(int i=;i<n;i++)
{
cin>>a[i];
}
cin>>k>>d;
for(int i=;i<n;i++)//初始化
{
mx[i][]=mn[i][]=a[i];
}
for(int i=;i<n;i++)
{
for(int j=;j<k;j++)
{
for(int m=i-;m>=max(,i-d);m--)//因为相邻位置编号差不超过d,所以i-(i-1)<=d,---->i-1>=i-d;
{
mx[i][j]=max(mx[i][j],max(mx[m][j-]*a[i],mn[m][j-]*a[i]));
mn[i][j]=min(mn[i][j],min(mx[m][j-]*a[i],mn[m][j-]*a[i]));//因为能力值有负值,所以负数最小也要考虑
}
}
}
ll ans=mx[][k-];
for(int i=;i<n;i++)
{
ans=max(ans,mx[i][k-]);
}
cout<<ans<<endl;
return ;
}
最新文章
- Objective-C快速上手
- IAR FOR ARM的安装及破解
- android 使用HttpURLConnection方式提交get/post请求
- 第05篇. Tomcat和JDK的内存配置
- 天气预报接口api(中国天气网)
- iOS - VIPER 架构模式
- T-SQL openquery 删除报错 “键列信息不足或不正确。更新影响到多行”
- iOS开发——Block详解
- [week4]每周总结与工作计划
- Verdigris: Qt without moc
- maven使用.02.一些概念
- 使用Maven来创建WEB项目
- MyBatis记录
- Java 读书笔记 (七) 变量
- 关于Oracle配置一些需要注意地方(IIS相关)
- tensorflow/core/kernels/conv_ops.cc:659] check failed: stream->;parent()->;getc
- Python 21 Django 实用小案例1
- 20155326刘美岑 《网络对抗》Exp1 PC平台逆向破解
- Struts的JSON机制
- C API 连接MySQL及批量插入