洛谷 - P2389 电脑班的裁员

#题面

#题目背景

隔壁的新初一电脑班刚考过一场试，又到了 BlingBling 的裁员时间，老师把这项工作交给了 ZZY 来进行。而 ZZY 最近忙着刷题，就把这重要的任务交（tui）给了你。

#题目描述

ZZY 有独特的裁员技巧：每个同学都有一个考试得分 $a_i$，在 $n$ 个同学中选出不大于 $k$ 段相邻的同学留下，裁掉未被选中的同学，使剩下同学的得分和最大。要特别注意的是，这次考试答错要扣分，所以得分有可能为负。

#输入格式

第一行为 $n, k$，第二行为第 $1 \sim n$ 位同学的得分。

#输出格式

一个数 $s$，为最大得分和。

#输入输出样例

输入样例 #1

5 3
1 -1 1 -1 1

输出样例 #1

3

#数据范围与约定

对于 $100\%$ 的数据，$k \leq n \leq 500$，$|a_i| \leq 10^3$。

#思路

动态规划，时间复杂度 $O(n^3)$。

设 $f_{i, j}$ 表示前 $i$ 个数取 $j$ 段的最大价值。

• 若不选 $a_i$ 则 $f_{i, j} = f_{i - 1, j}$；
• 若选择 $a_i$ 则需要枚举最后一段的起始位置 $l$：$f_{i, j} = f_{l, j - 1} + \sum_{p = l}^{i} a_p (l \in [j - 1, i])$。

整理得转移方程：

$$f_{i, j} = \max\{f_{i, j}, f_{i - 1, j}, f_{l, j - 1} + \sum_{p = l + 1}^{i} a_p\}$$

#代码

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

#include <algorithm>
#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 505;

int n, k, sum[N], f[N][N];

int main() {
    std::ios::sync_with_stdio(false);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum[i] = sum[i - 1] + x;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            for (int l = j - 1; l <= i; l++) {
                f[i][j] = std::max({f[i][j], f[i - 1][j], f[l][j - 1] + (sum[i] - sum[l])});
            }
        }
    }

    cout << f[n][k] << endl;

    return 0;
}