牛客网-网易2017笔试 合唱团(dp)

题目来源:合唱团

题目描述

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

输入描述:

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

输出描述:

输出一行表示最大的乘积。

输入

3
7 4 7
2 50

输出

49

思路

给出 n 个数字,要求按顺序选择 k 个,使得选出的数的乘积最大。且要求选择的相邻两个人的距离必须小于等于 d.

定义 dp[n][k] 为以位置为 n 的人为结尾(位置为 n 的人就是选择的第k个人),选择 k 个人(包括自己)所能获得的最大乘积

那么问题的答案就是扫一遍 dp[k][k]...dp[n][k] 所得的最大值就是答案。

但是这里面包含负数,所以我们要把 dp 拆成两个来定义:

  • dp_max[i][j]:以第 i 个人为结尾,选择 j 个人所能获得的最大乘积
  • dp_min[i][j]:以第 i 个人为结尾,选择 j 个人所能获得的最小乘积

现在的问题是,我们知道当前选择的第 k 个人是位置为 n 的人,那么选择的第 k-1 个人的位置在哪里?

首先有,第 k-1 个人的位置一定>=k-1(如果从1开始每一个都选,那么它只能到k-1)

我们看一下题目上的约束条件,要求选择的两个人相邻的距离必须小于等于 d ,那么他的位置一定 >=n-d,因为必须小于等于 d.

且 他的位置一定是小于等于 n-1 的.

所以假设我们要算的第 k-1 个人的位置为 l ,那么满足 max(k-1,n-d)<=l<=n-1.

因为数里面有负数,所以我们dp的时候,

$dp_{max}[i][j] = max(dp_{max}[i][j], max(dp_{max}[l][j - 1] * a[i], dp_{min}[l][j - 1] * a[i]))$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const ll N = 50 + 10;
ll a[N], dp_max[N][N], dp_min[N][N];
int main()
{
    //freopen("in.txt", "r", stdin);
    ll n, k, d;
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        dp_max[i][1] = dp_min[i][1] = a[i];
    }
    scanf("%lld%lld", &k, &d);
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = 2; j <= k; j++)
        {
            if (i >= j)
                for (ll l = max(j - 1, i - d); l <= i - 1; l++)
                {
                    dp_max[i][j] = max(dp_max[i][j], max(dp_max[l][j - 1] * a[i], dp_min[l][j - 1] * a[i]));
                    dp_min[i][j] = min(dp_min[i][j], min(dp_max[l][j - 1] * a[i], dp_min[l][j - 1] * a[i]));
                }
        }
    }
    ll ans = -inf;
    for (ll i = k; i <= n; i++)
        ans = max(ans, dp_max[i][k]);
    printf("%lld\n", ans);
    return 0;
}
最后修改:2018 年 12 月 30 日 04 : 30 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论