题目大意 给定一个长度为 $n$ 的数组 $a\ (-10^9 \le a_i \le 10^9)$，我们可以把它分割成任意个连续的子序列 $s_k = a_l \ldots a_r$，每段子序列的权值为：
$\sum_{j=l}^{r} a_j > 0$ 时，权值为 $r - l + 1$
$\sum_{j=l}^{r} a_j = 0$ 时，权值为 $0$
$\sum_{j=l}^{r} a_j < 0$ 时，权值为 $-(r - l + 1)$
求出让所有子序列权值之和最大的一种分割方法。
题目链接
思路 我们可以先按照动态规划的思路来写出状态转移方程，设 $f_i$ 是在 $i$ 之前可以获得最大权值，$calc(i,j)$ 是计算相应子序列的权值。那么：
我们继续观察它，假如 $a[i]$ 加上前面的子序列都是负数，那么我们就完全可以让 $a[i]$ 单独成一个子序列，这样它对答案的减少只有 $-1$。
也就是说，我们计算 $a[i]$ 时，我们只用考虑位置在它前面且前缀和小于它的位置 。
但是即使只考虑这些，遍历所有的 $j < i$ 还是会TLE :(
不过我们发现，如果我们只考虑在它前面且前缀和小于它的位置，那么上面状态转移方程可以化简为：
进一步推导发现 $f[i] = \max(f[j] - j) + i$。再往下化简一步：
而 $\max(f[j] - j)$ 可以较快速地求出。
具体来说，我们把前缀和 $sum$ 数组排序，比如 $sum[2]$ 排序后的位置是 $4$，那么我们更新 $f[2]$ 的时候就查看树状数组中 $4$ 之前的最大值，插入 $f[2] - 2$ 时，就放入树状数组中的位置 $4$。
遍历的时候还是按照原来的顺序，这样既能按照动态规划的正确形式更新答案，也能正确维护树状数组。
代码 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 #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std;const int maxN = 5e5 + 78 ;const long long INF = 0x7f7f7f7f ;int T, n, cnt, order[maxN];long long a[maxN], f[maxN], c[maxN], sum[maxN];pair<long long , int > t[maxN]; inline void add (int pos, long long val) for (; pos <= n; pos += (pos & -pos)) c[pos] = max (c[pos], val); } inline long long ask (int pos) long long tmp = -INF; for (; pos > 0 ; pos -= (pos & -pos)) tmp = max (tmp, c[pos]); return tmp; } int main () scanf ("%d" , &T); while (T--) { scanf ("%d" , &n); for (int i = 1 ; i <= n; ++i) { scanf ("%lld" , &a[i]); sum[i] = sum[i - 1 ] + a[i]; t[i] = {sum[i], -i}; } for (int i = 1 ; i <= n; ++i) { c[i] = f[i] = -INF; } sort (t + 1 , t + 1 + n); for (int i = 1 ; i <= n; ++i) order[-t[i].second] = i; for (int i = 1 ; i <= n; ++i) { f[i] = f[i -1 ] + (a[i] == 0 ? 0 : a[i] / abs (a[i])); f[i] = max (f[i], ask (order[i]) + i); if (sum[i] > 0 ) f[i] = i; add (order[i], f[i] - i); } printf ("%lld\n" , f[n]); } return 0 ; }
