要是正开的话,结果会不一样吗?
做题顺序:C->A->C->B。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意解析:给定一个初始长度为 nnn 的数组 AAA。你需要对 AAA 进行 n−1n-1n−1 次操作。每次操作如下:
* 你可以选择 A1A_1A1 或 A2A_2A2 。
* 如果你选择 A1A_1A1 ,将得分增加 A1A_1A1 ,并删除 A1A_1A1 。
* 如果你选择 A2A_2A2 ,将得分增加 −A2-A_2−A2 ,并删除 A2A_2A2 。
* 将剩余元素重新编号。
求最大得分。
n≤2×105,1≤−109≤Ai≤109n\le 2\times 10^5,1\le\red{-10^9}\le A_i\le 10^9n≤2×105,1≤−109≤Ai ≤109。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思考半小时贪心无果,于是先打个 DP 再说。
注意到最终会剩一个元素,而那个元素是最终的 A1A_1A1 。
所以我们可以记 dp[i][j]\text{dp}[i][j]dp[i][j] 为前 i−1i-1i−1 操作后 A1A_1A1 是原来的 AjA_jAj ,于是就有了很显然的 DP:
dp[i][j]={maxk=1i−1(dp[i−1][k]+Ak)j=idp[i−1][j]−Aij<i\text{dp}[i][j]= \begin{cases} \max_{k=1}^{i-1}(\text{dp}[i-1][k]+A_k) & j=i\\ \text{dp}[i-1][j]-A_i & j<i\\ \end{cases} dp[i][j]={maxk=1i−1 (dp[i−1][k]+Ak )dp[i−1][j]−Ai j=ij<i
注意到这个很可以优化的样子!
首先滚动数组一下,记第 i−1i-1i−1 次操作前的 DP 数组为 dp\text{dp}dp,操作后的 DP 数组为 dp′\text{dp}'dp′,则有如下:
dp′[j]={maxk=1i−1(dp[k]+Ak)j=idp′[j]=dp[j]−Aj j<i\text{dp}'[j]= \begin{cases} \max_{k=1}^{i-1} (\text{dp}[k]+A_k) & j=i\\ \text{dp}'[j]=\text{dp}[j]-A_j\space\space & j\lt i \end{cases} dp′[j]={maxk=1i−1 (dp[k]+Ak )dp′[j]=dp[j]−Aj j=ij<i
显然我们需要一个方法可以快速求出 maxdp[k]+Ak\max \text{dp}[k]+A_kmaxdp[k]+Ak ,还要将它整体减 AjA_jAj 。
考虑一个新的 DP,dp[j]\text{dp}[j]dp[j] 为原来的 dp[j]+Aj\text{dp}[j]+A_jdp[j]+Aj ,这样就转化成了:
dp′[j]={maxk=1i−1dp[k]j=idp′[j]=dp[j]−Aj j<i\text{dp}'[j]= \begin{cases} \max_{k=1}^{i-1} \text{dp}[k] & j=i\\ \text{dp}'[j]=\text{dp}[j]-A_j\space\space & j\lt i \end{cases} dp′[j]={maxk=1i−1 dp[k]dp′[j]=dp[j]−Aj j=ij<i
最终答案:
ans=maxi=1ndp[i]−Ai\text{ans}=\max_{i=1}^n \text{dp}[i]-A_i ans=i=1maxn dp[i]−Ai
注意这样最开始的 dp[1]\text{dp}[1]dp[1] 应该为 A1A_1A1 而不是 000。
好了,顺眼多了。那就可以用线段树维护了。
时间复杂度:O(nlogn)O(n\log n)O(nlogn)。