Loj鏈接：接竹竿

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

題目大意：

給定一個數組，每次加入一種顏色的數，可以取走與它顏色相同的兩個數之間的所有數，問最後取走的所有數中最大和是多少

分析：

第一眼看到的是二分答案，但不知道二分的check()函數怎麼寫。

沒辦法，考慮DP（其實是因為我貪心寫掛了）

DP如果可以，那麼要至少要滿足一下幾個條件：

1. DP前面的選擇情況不影響後面的選擇情況（前不影響後）
2. 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轉移方程。

接下來就考慮優化唄！

優化

1. 首碼和優化

易發現，DP方程里有很多類似求$\sum_{i}^{j} v_k$的，並且每次DP推方程時都要重新計算一遍

其實，求連續一段值的和，我們可以用首碼和優化啊！

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

示例代碼（會TLE!）：

for(int i=1;i<=n;i++) scanf("%lld",&a[i].y),a[i].y+=a[i-1].y;
for(int i=1;i<=n;i++)
{
    dp[i]=dp[i-1];
    for(int j=1;j<i;j++)
    if(a[i].x==a[j].x) dp[i]=max(dp[i],dp[j-1]+a[i].y-a[j-1].y);
}

考慮進一步優化

發現轉移時，只能找與自己顏色相同的進行轉移，所以可以把每一個顏色記錄下來，省下迴圈過程。

這可以用鏈表或者$ \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)}$

Code:

#include<bits/stdc++.h>
#define L long long
using namespace std;
struct P{
    int x;
    L y;
}a[1000005];
L dp[1000005],maxx[1000005];
signed main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].x);
    for(int i=1;i<=k;i++) maxx[i]=-1e18;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i].y),a[i].y+=a[i-1].y;
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i-1],maxx[a[i].x]+a[i].y);
        maxx[a[i].x]=max(maxx[a[i].x],dp[i-1]-a[i-1].y);
    }
    printf("%lld",dp[n]);
    return 0;
}