小p的单调数列

Posted on In

题目大意:我们定义个数列的价值为:将这个数列顺次划分为若干个极长单调区间(相邻两个单调区间的单调性不必相同)后,每个单调区间中元素总和的平均值.(第一个区间强制规定为递增的)想在想问你在给定的序列中,价值最大的是哪个子序列.(严格单调,不存在等于的情况)

这个题目废话很多,但是最废话的是这么一句:相邻两个单调区间的单调性不必相同.

我认为只要保证第一个区间是递增的(符合题解),后边随意就行.

考虑反证:后边有个区间也是递增的,那么如果后边区间的第一个数字比我当前递增区间的最后一个数字还要大,那么我显然可以接上去,把两个合并为一个;如果后边那个区间是递减的,符合题意.

证毕.

再来考虑答案的最有性选择.结论:最优的一定出自一条递增的区间或者一条递增和一条递减的区间

证明:

假设上图中靠上部分的"1-2-3"为当前答案,"3-4"为新找到的答案

设ans为原先答案,x为新找到的答案,

考虑合并之后的答案:\(\dfrac {ans \times 2 + x} 3\)

解方程\(ans < \dfrac {ans \times 2 + x} 3\)

所以\(ans < x\)

那么显然x单独作为答案更合理,因为他加上一个比他小的数字,显然不如自己一个人大(因为答案是求平均值)

对于上图靠下部分的"5-6-7"为当前答案,"7-8"为新找到的答案

读者自证不难

代码很好写,dp的同时用树状数组来维护

其中\(f_i\)表示以i为结尾的最长的递增权值,\(g_i\)是同理,只不过是递减的

代码如下: 

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define int long long
#define ll long long
using namespace std;

const int N = 1e5 + 66;

int n, cnt;
int a[N], b[N], d[N], f[N], g[N], tree[N];
double res;

inline void updata(int x, int val)
{
    while (x <= cnt)
    {
        tree[x] = max(tree[x], val);
        x += lowbit(x);
    }
    return;
}

inline int query(int x)
{
    int ret(0);
    while (x)
    {
        ret = max(ret, tree[x]);
        x -= lowbit(x);
    }
    return ret;
}

signed main()
{
    int i; n = read();
    for (i = 1; i <= n; ++ i) b[i] = a[i] = read();

    sort(b + 1, b + 1 + n);
    cnt = unique(b + 1, b + 1 + n) - b - 1;

    for (i = 1; i <= n; ++ i)
    {
        d[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
        f[i] = query(d[i] - 1) + a[i];
        updata(d[i], f[i]);
    }
    for (i = 1; i <= cnt; ++ i) tree[i] = 0;
    for (i = n; i >= 1; -- i)
    {
        g[i] = query(d[i] - 1) + a[i];
        updata(d[i], g[i]);
    }

    for (i = 1; i <= n; ++ i) res = max(res, max(f[i] / 1.000, (f[i] + g[i] - a[i]) / 2.000));
    printf ("%.3lf\n", res);

    return 0;
}

后记:

实在是思维极其巧妙的树状数组优化dp题目

膜拜出题人的巧妙灵感

膜拜建业大佬考场一遍切题!