- 题解
CSP 2024T3 染色
-
(Congratulations!)国贸王沐阳 LV 8 (47/47) @ 2025-4-12 19:54:03
一道dp题 考虑 dfs 暴力，枚举每一个位置的颜色，记录当前位置上一个的红色和蓝色的数的值，在中途统计答案。时间复杂度：O（)。考虑将 dfs 暴力转化为 dp，将 dfs 中记录的状态转化为$$f_i$$$$_j$$$$_k$$，表示选到第$$i$$个，从第$$i$$个数起，从右往左第一个红色数为$$j$$，第一个蓝色数为$$k$$，转移和 dfs 基本一样。时间复杂度O（)。 容易发现一个性质，我们没必要将j和k都记录下来，因为j和k中一定有一个为$$a_i$$，这样又可以把状态设计为$$f_i,$$$$_j,$$$$0$$$$/$$$$_1$$表示选到第i个数第i个数的颜色为0/1（红或蓝），上一个与第i个数异色的数为j的最大代价。转移方程为： $$f_i$$$$_j$$$$o$$<——$$f_i$$$$-$$$$_1$$$$_j$$$$_o$$+a$$_i
$$[a$$_i$$=a$$_i$$$$_-$$$$_1$$] $$f_i$$a$$_i$$$$_-$$$$_1$$$$_,$$$$_o$$<——max{f$$_i$$$$_-$$$$_1$$$$_j$$$$_o$$+j[j=$$a$$$$_i$$]}对于这三个转移式，我们首先可以将i通过滚动数组滚掉，然后可以维护一个全局max和一个全局加的tag,这样就可以做到O（$n$)的转移了。 代码启动！ ```cpp #include3 条评论
-
(未来の鳩（お互い）)国贸单滢睿 LV 9 (37/37) @ 2025-4-12 21:17:22
？！
-
@ 2025-4-12 19:55:26
我太牛了
-
@ 2025-4-12 19:55:12
#include<bits/stdc++.h> #define int long long const int N=1e6+5; using namespace std; int a[N],last[N],f[N],sum[N],n,inf; inline void upd(int &x,int y){ x=(x>y?x:y); } void work(){ cin>>n; for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); last[a[i]]=0;f[i]=0; sum[i]=sum[i-1]; sum[i]+=(a[i]==a[i-1]?a[i]:0); } for(int i=1;i<=n;i++){ f[i]=f[i-1]; if(last[a[i]]){ int j=last[a[i]]+1; upd(f[i],f[j]+a[i]+sum[i]-sum[j]); } last[a[i]]=i; } printf("%lld\n",f[n]); } #undef int int main(){ int T; cin>>T; while(T--){ work(); } return 0; }
- 1