CSP-S 2024 T3 染色 题解

题目大意：

将$a$数组染色后计算最大得分
应该都知道

思路：

首先，这是一道$dp$题
由题目，对于每个$a_{i}$，如果我们想要计算$a_{i}$的分，那么从$i$到$lst_{a_{i}}$之间应都与$a_{i}$异色
则若我们要加上$a_{i}$，仅能计算$a_{lst_{i}+1}$产生的得分，因为$a_{lst_{i}+1}$可以与之前的$a_{j}$同色，从而加分
所以易得转移方程：

dp[i]=max(dp[i-1],dp[lst[a[i]]+1]+a[i]);

还有一点
如果$a_{i}=a_{i-1}$
此时可以直接加上$a_{i}$的分数
因为无论如何同色都优于异色
即:

if(a[i-1]==a[i]){ 
    ans+=a[i];
    dp[i]=dp[i-1];
    lst[a[i]]=i;
    continue;
}

所以就可以写出某抽象小代码~~~~
然后一交，诶：

65分
无需多言

十年OI一场空，不开longlong见祖宗

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long //不开longlong见祖宗~
int n,a[200005],dp[200005],lst[1000005];//lst:上一个该数字出现的位置
void solve(){
    memset(dp,0,sizeof(dp));
    memset(lst,0,sizeof(lst));
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i];
    int ans=0;
    lst[a[1]]=1;
    for(int i=2;i<=n;i++){
        if(a[i-1]==a[i]){ //如果相邻数字相同直接计算得分
            ans+=a[i];
            dp[i]=dp[i-1];
            lst[a[i]]=i;
            continue;
        }
        if(lst[a[i]]){ //存在上一个该数字
            dp[i]=max(dp[i-1],dp[lst[a[i]]+1]+a[i]);//是否选择计算a[i]的得分
            lst[a[i]]=i;
        }else{
            dp[i]=dp[i-1];
            lst[a[i]]=i;
        }
    }
    cout << ans+dp[n] << endl;
}
signed main(){
    int t;cin >> t;
    while(t--)solve();
}

我也不知道为啥那么慢