杂题——序列分段

序列分段

原题

题目描述

给定一个正整数序列{a n}，你需要将其划分成k段连续且不相交的子段，我们定义一种划分的完美度为每个子段的中位数之和。

  • 在这里，我们定义一个序列a1,a2,…,a n(a1≤a2≤…≤a n)的中位数为：a[⌊（n+1）/ 2⌋]
  • 例如：1,6,4,2,5,3的中位数为3，因为将其排序后为：1,2,3,4,5,6，取第⌊（6+1）/2⌋=3个数即为3.

你需要找到一个完美度最大的划分方案。

输入描述

第一行两个整数,N,K(1≤K≤N≤300)

接下来一行N个整数，用空格间隔，分别表示a1,a2,…,a n(1≤a i≤106)

输出描述

一行一个整数，代表最大的完美度。

样例输入

1
2
8 3
6 9 2 4 7 8 2 1

样例输出

1
17

提示

样例解释：

将序列分为：[2,4,7,8,2,1]，则三段的中位数之和为：6+9+2=17

可以证明不存在更优的划分方案。

思路

​ 这道题目是DP问题中比较常见的一种类型，当我们遇到将一个数组分为若干组这样的题眼的时候我们就可以联想到这道题目的编写思路了，比如说leetcode还有其他地方都有和这个题目非常类似的题目，只不过它们的属性稍微变了一下，这道题目是中位数最小值，而其他题目比如说410.分割数组的最大值的属性是数组区域的和。

​ 思路： 首先我们定义一个数组f[i] [j] 表示前i个数划分成j组的最大完美值，那么我们该如何求它的最大值呢？很简单，我们可以首先将前i个数分为两部分，第一部分是0k,第二部分是k + 1 ~ i,前面一部分已经被划分成了j - 1段，后一部分则是我们需要求的，这里可以举个例子来加深一下理解：比如说对于前5个数，我们要求划分3段的完美度的最大值，那么我们只需要求00, 15; 01,25; 02,35; 03,45; 04;5~5; 这些组合的最大值即可求出f[i] [j]的最大值，详细部分请看代码。

代码

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
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 310;
int f[N][N], b[N], s[N][N];

int main()
{
  int n, kk;
  cin >> n >> kk;
  
  for (int i = 1; i <= n; i++) cin >> b[i];
  
    // 预处理所有区间的中位数
    for (int len = 1; len <= n; len ++)
        for (int i = 1; i + len - 1 <= n; i ++)
        {
            int j = i + len - 1;
            int temp[N] = {0};
            int t = 1;
            for (int k = i; k <= j; k ++)
                temp[t ++] = b[k];
            sort(temp + 1, temp + t);
            s[i][j] = temp[(len + 1) / 2];
        }
          
//   // 前i个数有着j段，按照k在i、j之间的位置来进行划分，分别实际上就是i,k和k + 1,j所有位置进行枚举然后找出
//   // 所有情况中的完美度最大情况
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= kk; j++) {
            for (int k = 0; k < i; k++) {
                f[i][j] = max(f[i][j], f[k][j - 1] + s[k + 1][i]);
            // cout << i << " " << k << " " << check(k + 1,i) << '\n';
            }
        }
    }  

  cout << f[n][kk];
  return 0;
}