Skip to content

洛谷 - P2389 电脑班的裁员

题解586 字
检测到 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\}

代码

#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;
}