题目大意
给定一个长度为\(n\)的数组\(a(-10^9 \le a_i \le 10^9)\)。 我们可以把它分割成任意个连续的子序列。 每个子序列\(s_k = a_l...a_r\)会有一个权值: * \(\sum_{j=l}^{r}a_i > 0\),则权值为\(r - l + 1\) * \(\sum_{j=l}^{r}a_i = 0\),则权值为\(0\) * \(\sum_{j=l}^{r}a_i > 0\),则权值为\(-(r - l + 1)\)
求出让所有子序列权值之和最大的一种分割方法。 题目链接 ## 思路 我们可以先按照动态规划的思路来写出状态转移方程,设\(f_i\)是在\(i\)之前可以获得最大权值,\(calc(i,j)\)是计算相应子序列的权值。 那么: \[f[i] = max(f[j] + calc(j + 1, i)),1 \le j \le i\] 我们继续观察它,假如\(a[i]\)加上前面的子序列都是负数,那么我们就完全可以让\(a[i]\)单独成一个子序列,这样它对答案的减少只有\(-1\)。
也就是说,我们计算\(a[i]\)时,我们只用考虑位置在它前面且前缀和小于它的位置。
但是即使只考虑这些,我们需要遍历所有的\(j, j < i\)还是会TLE : (
不过我们发现,如果我们只考虑在它前面且前缀和小于它的位置,那么上面状态转移方程可以化简为: \[f[i] = max(f[j] + (i - j),1 \le j \le i\](因为我们只选择和为正数的子序列) 进一步推导发现\(f[i] = max(f[j] - j + i)\) 再往下化简一步: \[f[i] = max(f[j] - j) + i,1 \le j \le i\]
而\(max(f[j] - j)\)可以较快速的求出。
具体来说,我们用把前缀和sum数组排序,比如\(sum[2]\)排序后的位置是\(4\),那么我们更新\(f[2]\)的时候就查看树状数组中\(4\)之前的最大值。。插入\(f[2] - 2\)时,就把放入树状数组中的位置\(4\)。
遍历的时候还是按照原来的顺序,这样既能按照动态规划的正确形式更新答案,也能正确维护树状数组。
代码
1 |
|