Loj链接：接竹竿

$ {\scr \color {SkyBlue}{\text{Solution}}} $

题目大意：

给定一个数组    
    
    
，每次加入一种颜色的数    


     


     


   ，可以取走与它颜色相同的两个数之间的所有数




 




 




 

，问最后取走的所有数中最大和是多少

分析：

第一眼看到的是二分答案   

   

   

，但不知道二分的check()函数怎么写    
    
    
。

没办法     

     

     

  ，考虑DP（其实是因为我贪心写挂了）

DP如果可以




  




  




  
，那么要至少要满足一下几个条件：

时间    
    
    
、空间复杂度等可以以后慢慢优化啦！

尝试一下？

尝试列出转移方程：

$$dp[i]=max \begin{cases} dp[i-1]& \text{$c_i$}!={c_j}\\ dp[j-1] + \sum_{k=1}^{i} v_k - \sum_{k=1}^{j-1} v_k& \text{$c_i==c_j$} \end{cases}$$

这样我们就列出了一个$O(n^3)$的DP转移方程    


     


     


   。

接下来就考虑优化呗！

易发现
  


  


  


，DP方程里有很多类似求$\sum_{i}^{j} v_k$的     
     
     
 ，并且每次DP推方程时都要重新计算一遍

其实 




   




   




   ，求连续一段值的和

 



 



 



，我们可以用前缀和优化啊！

现在方程就是$O(n^2)$的了




 




 




 

。

示例代码（会TLE!）：

考虑进一步优化

发现转移时               ，只能找与自己颜色相同的进行转移  




    




    




    ，所以可以把每一个颜色记录下来
















，省下循环过程   

   

   

。

这可以用链表或者$ \cal{vector}$ 实现

注意:时间复杂度此时是可以被卡到O(n^2)的！因为并没有剩下转移过程               ，只是省去了枚举无法转移情况的时间     

     

     

  。

代码就不放辣QwQ!

再来看看这个转移方程:

$$dp[i]=max \begin{cases} dp[i-1]& \text{$c_i$}!={c_j}\\ dp[j-1] + \sum_{k=1}^{i} v_k - \sum_{k=1}^{j-1} v_k& \text{$c_i==c_j$} \end{cases}$$

我们可以把\cal{dp[i]}的初值赋为$\cal{dp[i-1]}$

那就只要考虑这个:

$$dp[i]=max \begin{cases} dp[j-1] + \sum_{k=1}^{i} v_k - \sum_{k=1}^{j-1} v_k& \text{$c_i==c_j$} \end{cases}$$

用前缀和优化后：

$$dp[i]=max \begin{cases} dp[j-1] + summ[i]- summ[j-1] & \text{$c_i==c_j$} \end{cases}$$

我们稍稍改变一下转移方程顺序：

$$dp[i]=max \begin{cases} summ[i]+(dp[j-1] - summ[j-1]) & \text{$c_i==c_j$} \end{cases}$$

换句话说   



     



     



    ，我们只要求出与$c_i$相等颜色里
















，$dp[j-1] - summ[j-1] $ 最大值

这个可以用一个数组记下来啊！

那么只要$\cal{O(1)}$    
    
    
，就能完成转移

时间复杂度：$ \cal{O(n)}$