WA了半天,水一份题解纪念一下,求赞QWQ
这是一道DP题:
- 状态表示:
dp[n]
表示只用 $1-n$ 的数字能得到的符合要求的区间的长度的和的集合- 性质: 维护这个集合的最大值
注意 : $s$ 数组为前缀和数组
状态转移:
1.用第 $i$ 个数字:则 $i$ 为某个区间的结尾,这时可以从 $dp[j]$ ($1\leq j < n ,s[j] <= s[i]$)通过
$$dp[i] = \max(dp[i],dp[j] + i - j)$$
2.不用第 $i$ 个数字:直接由 $dp[i - 1]$ 转移
$$dp[i] = \max(dp[i],dp[i - 1])$$
3.特判一下 $s[i] \geq 0$ 的情况,此时最大值容易看出是 $dp[i] = i$
优化第一步转移: 维护满足小于 $s[i]$ 的 $s[j]$ 对应的 $dp[j] - j$ 的最大值
于是可以使用能够维护前缀最值的数据结构: 树状数组,线段树,平衡树(可能改一下能用,没写过类似的)
WA半天+1