題目鏈接

[CSP-S 2024] 染色

題解

這是一道線性 \(dp\) 問題，難點(diǎn)在于在具體的題目背景中抽象出實(shí)際問題，最難的地方是分類討論。
根據(jù)題目的意思，如果第 \(i\) 位數(shù)字（\(a_{i}\)）的顏色和第 \(i\) 位之前的數(shù)字（\(a_{[1,i]}\)）的顏色都不同，則這個(gè)數(shù)字貢獻(xiàn)為 \(0\)，接著，如果前面有相同的顏色，再如果離第 \(i\) 位最近的相同顏色的數(shù)字和第 \(i\) 數(shù)字相同，則第 \(i\) 位數(shù)字貢獻(xiàn)為 \(a_{i}\)。我們只討論這個(gè)數(shù)可以有貢獻(xiàn)時(shí)的情況，當(dāng)這個(gè)數(shù)無論如何也無法貢獻(xiàn)時(shí)不進(jìn)行討論，我們用結(jié)構(gòu)體存 \(a_{i}\) 這個(gè)數(shù)字在之前出現(xiàn)過的位置的下標(biāo)以及這個(gè)數(shù)字本身：

struct num{
    ll n,last;
}a[2000005];

當(dāng) \(a_{i}\) 在之前沒有出現(xiàn)過時(shí)，后文用 \(a_{i}(last)\) 表示 \(a_{i}\) 這個(gè)數(shù)字在之前出現(xiàn)過的位置的下標(biāo)，\(a_{i}(last)=0\) ，接下來討論以下情況

• 兩個(gè)相同的數(shù)相鄰（\(a_{i}=a_{i-1}\)），這樣的兩個(gè)數(shù)，只要顏色相同，無論如何都會(huì)產(chǎn)生貢獻(xiàn)，但是對(duì)后續(xù)有影響（請(qǐng)先看下文）
• 兩個(gè)相同數(shù)不相鄰，存在 \(i>j\)，\(a_{i}=a_{j}\) ,那么要想讓 \(a_{i}\) 產(chǎn)生貢獻(xiàn)，\(a_{[i+1,j-1]}\) 區(qū)間內(nèi)的數(shù)字必須是同一顏色且和 \(a_{i} \ ,\ a_{j}\) 的顏色不同，那么對(duì)于 \(a_{[i+1,j-1]}\) 內(nèi)的數(shù)字，如果存在兩個(gè)相同的數(shù)，但這兩個(gè)數(shù)又不相鄰，它們的貢獻(xiàn)就沒有了。
• 兩組相同的數(shù)交叉，如果想讓兩組數(shù)都產(chǎn)生貢獻(xiàn)，必須滿足下列狀態(tài)：

x,...,y,x,...,y

如果是下面這種狀態(tài)，只能使其中一組產(chǎn)生貢獻(xiàn)：

x,...,y,...,x,...,y

經(jīng)過上面的分類討論后，我們?cè)O(shè) \(f_{i,j=0/1}\) 表示對(duì)于前 \(i\) 個(gè)數(shù)字，當(dāng) \(j=0\)，表示第 \(i\) 個(gè)數(shù)字與第 \(a_{i}(last)\) 不產(chǎn)生貢獻(xiàn)時(shí)的最優(yōu)解，當(dāng) \(j=1\) 時(shí)，表示第 \(i\) 個(gè)數(shù)字與第 \(a_{i}(last)\) 產(chǎn)生貢獻(xiàn)時(shí)的最優(yōu)解。如果兩個(gè)數(shù)字既相鄰又相同，要把他們的貢獻(xiàn)算進(jìn)最后的答案里，但是在表示狀態(tài)時(shí)，必須表示成沒有產(chǎn)生貢獻(xiàn)的狀態(tài)。如果出現(xiàn)交叉情況，直接訪問 \(a_{i}(last)\) 和 \(a_{i}(last)+1\) 兩個(gè)位置上的數(shù)值即可。易得到狀態(tài)轉(zhuǎn)移方程式：

• 普遍情況：
  \( f_{i,0}=\max (f_{i-1,1}\ ,\ f_{i-1,0}) \)
  \( f_{i,1}=\max (f_{a_{i}(last),1}\ ,\ f_{{a_{i}(last)},0} \ ,\ f_{a_{i}(last)+1,1}\ ,\ f_{{a_{i}(last)+1},0})+a_{i} \)
• 出現(xiàn)相鄰兩數(shù)的情況時(shí)：
  \( f_{i,0}=\max (f_{i-1,1}\ ,\ f_{i-1,0}) \)
  \( f_{i,1}=f_{i,0} \)
  將所有出現(xiàn)過的相鄰相同兩數(shù)加在一起，記為 \(anstmp\) ，最終答案就是 \(\max(f_{n,0} \ ,\ f_{n,1}) \ + \ anstmp\)

CODE

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

ll t,anstmp;
ll dp[2000005][2];
ll lst[2000005];

struct num{
    ll n,last;
}a[2000005];

int main(){
    ll t;
    scanf("%lld",&t);
    while (t--){
        ll n;
        scanf("%lld",&n);
        memset(dp,0,sizeof(dp));
        memset(lst,0,sizeof(lst));
        anstmp=0;
        for (ll i=1;i<=n;i++){
            scanf("%lld",&a[i].n);
            if (lst[a[i].n]) a[i].last=lst[a[i].n];
            else a[i].last=0;
            lst[a[i].n]=i;
            if (a[i-1].n==a[i].n) anstmp=anstmp+a[i].n;
        }
        for (ll i=1;i<=n;i++){
            if (a[i].n==a[i-1].n){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=dp[i-1][1];
                continue;
            }
            else dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            if (a[i].last) dp[i][1]=max(max(dp[a[i].last][0],dp[a[i].last][1]),max(dp[a[i].last+1][0],dp[a[i].last+1][1]))+a[i].n;
        }
        printf("%lld\n",max(dp[n][0],dp[n][1])+anstmp);
    }
    return 0;
}