Skip to content

洛谷 - P2389 电脑班的裁员

题解567 字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目背景

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

#题目描述

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

#输入格式

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

#输出格式

一个数 ss,为最大得分和。

#输入输出样例

输入样例 #1

5 3
1 -1 1 -1 1

输出样例 #1

3

#数据范围与约定

对于 100%100\% 的数据,kn500k \leq n \leq 500ai103|a_i| \leq 10^3

#思路

动态规划,时间复杂度 O(n3)O(n^3)

fi,jf_{i, j} 表示前 ii 个数取 jj 段的最大价值。

  • 若不选 aia_ifi,j=fi1,jf_{i, j} = f_{i - 1, j}
  • 若选择 aia_i 则需要枚举最后一段的起始位置 llfi,j=fl,j1+p=liap(l[j1,i])f_{i, j} = f_{l, j - 1} + \sum_{p = l}^{i} a_p (l \in [j - 1, i])

整理得转移方程:

fi,j=max{fi,j,fi1,j,fl,j1+p=l+1iap}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;
}