牛客网-网易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

输出

思路

给出 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]))$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。