CF1668D

发表于 | 分类于 |

题面:https://codeforces.com/contest/1668/problem/D

大致题意:给定一个数列，随意划分该数列为非空子数列，规定子数列的值为：

  1. 子数列总和为正，则为其长度，即i-j+1
  2. 子数列总和为0，则为0
  3. 子数列总和为负，则为其长度的相反数

求数列子数列值总和的最大值

题解:设dp[i]为前i个元素的最大值，sum[i]为前i个元素的和，则dp[j]到dp[i]的状态转移为:

  • dp[i]=dp[j-1]+i-j+1 (sum[i]-sum[j-1]>0)
  • dp[i]=dp[j-1] (sum[j]=sum[i-1])
  • dp[i]=dp[j-1]+j-i-1 (sum[i]-sum[j-1]<0)

故我们维护dp[i]，每次需要向前遍历找最大值，时间复杂度为，糊不过这题

注意到找最大值时，i一定，故找dp[j-1]-(j-1)的最大值，因此我们想到用树状数组or线段树维护前i-1个元素的dp[j-1]-(j-1)的最大值(需要保证sum[i]-sum[j-1]>0)

问题：如何处理sum差的其他情况？

  1. 易知，对最终答案中的划分情况，我们可以将所有的非正子数列划分成长度为1的子数列而不影响结果，故我们将其考虑到状态转移方程中，即考虑a[i]的正负，通过dp[i-1]递推出dp[i]的可能值(注意dp[0]应为0)

因此，我们只需维护sum[i]-sum[j-1]>0且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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<stack>
#include<unordered_set>
using namespace std;
using ll = int64_t;
const ll INF = 0x7fffffff;
ll T, n, m, k;
ll tmp, a[500005], pre[500005], dp[500005], tree[500005];
void add(ll x,ll val)
{
    while(x<=n)
    {
        tree[x] = max(tree[x], val);
        x += x & (-x);
    }
}
ll ask(ll x)
{
    ll ans = -INF;
    while(x>0)
    {
        ans = max(tree[x], ans);
        x -= x & (-x);
    }
    return ans;
}
int main()
{
    T = 1;
    cin >> T;
    while(T--)
    {
        cin >> n;
        pre[0] = 0, dp[0] = 0;
        vector<ll> pos(n);
        for (ll i = 1; i <= n;i++)
        {
            cin >> a[i];
            pre[i] = pre[i - 1] + a[i];
            tree[i] = -INF;
            pos[i - 1] = i;
        }
        sort(pos.begin(), pos.end(), [&](ll i, ll j)
             { return pre[i] == pre[j] ? (j < i) : (pre[i] < pre[j]); });
        vector<ll> order(n + 1);
        for (ll i = 1; i <= n;i++)
        {
            order[pos[i - 1]] = i;
        }
        for (ll i = 1; i <= n;i++)
        {
            dp[i] = dp[i - 1] + (a[i] == 0 ? 0 : (a[i] > 0 ? 1 : -1));//非正子数列的情况
            dp[i] = max(dp[i], ask(order[i]) + i);//注意+i
            if(pre[i]>0)
            {
                dp[i] = i;
            }
            add(order[i], dp[i] - i);
        }
        cout << dp[n] << "\n";
    }
    return 0;
}