CF484D-Kindergarten

描述

有一组数,你要把他分成若干连续段。每一段的值,定义为这一段 数中最大值与最小值的差。 求一种分法,使得这若干段的值的和最大。 \(n < 1e6, a_i < 1e9\)

题解

第一步需要发现一个性质,即——最优划分下,划分数组的端点一定是该数组的最值。我们可以这样想,如果不是的话,则可以划分到其他数组,不仅可以保证最终和不减,还有可能使和增大。

第二步,需要顺着这个思路,发现第二个性质——最优划分下,划分数组一定单调。为了证明这个结论,我们假设最优划分下一个数组左端点为最小值为min,右端点为最大值max,中间有a>b不符合单调性,此时,不难发现将数组再划分为[min,a],[b,max]时,a-min+max-b>max-min,与假设此时为最优划分矛盾,故得证。

此时,我们似乎已经得到了一个贪心的做法,即每次遇到不单调的数就划分进入下一组,但是这个贪心的做法是错误的,考虑一组数据\(3,1,0,2\),如果按照贪心的策略,我们将会划分为两组\(3,1,0\)\(2\),但是显然,这组数据最优解为4,并不满足这样的划分策略。这个划分策略唯一错误的点就在于,当一个数前后快速改变单调性时,这个策略会将这个数划分给后一组,而漏考虑了划分给前一组的可能。如下图,贪心策略唯一不可以处理的情况就是极值划分给前一组更优的情况,即右侧的情况。

所以,为了比较极值点划分给前后哪个方案更优,我们考虑动态规划去达成全局的最优。

定义f[i]表示到第i个元素时的最优解,定义pre为在i前出现的最后一个极值点,则有转移方程:

1
f[i] = max(f[pre] + abs(a[pre + 1] - a[i]), f[pre - 1] + abs(a[pre] - a[i]));

程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N];
ll f[N];
int main()
{
int n, pre = 1;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 2; i <= n; i++)
{
f[i] = max(f[pre] + abs(a[pre + 1] - a[i]), f[pre - 1] + abs(a[pre] - a[i]));
if (((a[i] >= a[i - 1]) && (a[i] >= a[i + 1])) || ((a[i] <= a[i - 1]) && (a[i] <= a[i + 1]))) //更新极值位置
pre = i;
}
printf("%lld\n", f[n]);
return 0;
}
----- 本文结束 感谢阅读 -----
0%