合唱团 N个学生中选K个,相邻两个的位置编号不超过D,使得K个学生乘积最大
程序员文章站
2024-03-23 22:15:22
...
网易2016内推笔试题:
有 n 个学生站成一排,每个学生有一个能力值,从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,返回最大的乘积。 每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数,k 和 d (1 <= k <= 10, 1 <= d <= 50)。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<set>
#include<queue>
using namespace std;
inline long long max(long long a, long long b){
return (a > b) ? a : b;
}
inline long long min(long long a, long long b){
return (a > b) ? b : a;
}
int main(int argc, char * argv[])
{
int n, *a, k, d; // 选k个学生,位置编号不超过d
// 尤其注意, dp_max[i][k] 表示在前 i 个数中选 k 个数,使得乘积最大, 且第 i 个数必选!!!!!!
// 同理,dp_max[i][k] 表示在前 i 个数中选 k 个数,使得乘积最小, 且第 i 个数必选!!!!!!
long long dp_max[52][12], dp_min[52][12];
while (~scanf("%d", &n))
{
/*********** Input ****************/
a = new int[n + 1];
memset(a, 0, sizeof(int)*(n + 1));
for (int i = 0; i < 52;i++)
for (int j = 0; j < 12; j++)
{
dp_max[i][j] = 1;
dp_min[i][j] = 1;
}
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
cin >> k >> d;
/*********** Algorithm ****************/
// dynamic programing
// initial
dp_max[1][1] = dp_min[1][1] = a[1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++){
//
for (int s = 1; s <= d; s++){
if (i - s >= 1){
dp_max[i][j] = max(dp_max[i][j], dp_max[i - s][j - 1] * a[i]);
dp_max[i][j] = max(dp_max[i][j], dp_min[i - s][j - 1] * a[i]);
dp_min[i][j] = min(dp_min[i][j], dp_min[i - s][j - 1] * a[i]);
dp_min[i][j] = min(dp_min[i][j], dp_max[i - s][j - 1] * a[i]);
}
}
}
/*********** Output ****************/
long long ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, dp_max[i][k]);
printf("%lld\n", ans);
}
return 0;
}
上一篇: openstack 自己制作云桌面linux瘦客户机
下一篇: 汇编语言程序设计——基础知识