P11233 CSP-S 2024 染色
考试最后码方程忘记 \(a[i-1]\) 了，调不出来，只好 \(50pts\) 收尾。
思路
\(dp\) 的难点在于确定一段的颜色后，无法快速找到上一段相同颜色的结尾。
从这里入手，设 \(dp[i][0/1][0/1]\) 表示第 \(i\) 位颜色为 \(1/0\)，第三维表示是一段颜色的 \(0\) 开头或 \(1\) 结尾。
设 \(sum[i][j]\) 为 \([i,j]\) 为同一个颜色的得分，有递推式：
\[sum[i][j]=sum[i][j-1]+(a[j-1]==a[j])\times a[j] \]其中 \(i<j\) 且 \(sum[i][i]=0\)。
接下来考虑转移。
\(i\) 为一段颜色 \(0\) 的开头，\([j,i-1]\) 为一段颜色 \(1\)，那么上一段颜色 \(0\) 的结尾在 \(j-1\) 处。之所以从 \(dp[j][1][0]\) 转移是因为需要加上 \(j\) 与上一段 \(1\) 结尾的贡献。
\[dp[i][0][0]=\max_{j<i}(dp[j][1][0]+sum[j][i-1]+(a[j-1]==a[j])\times a[i]) \]类似的，有：
\[dp[i][1][0]=\max_{j<i}(dp[j][0][0]+sum[j][i-1]+(a[j-1]==a[i])\times a[i]) \]\(i\) 为一段颜色 \(0\) 的结尾，这段颜色的开头 \(j\) 可以是 \([1,i]\) 中任意一个点。
那么有 \(dp[i][0][1]=\max_{j\leq i}(dp[j][0][0]+sum[j][i])\)。
类似的 \(dp[i][1][1]=\max_{j\leqq i}(dp[j][1][0]+sum[j][i])\)。
观察 \(sum\) 的求法，发现本质上可以前缀和作差优化。
重新设 \(sum[i]\) 为 \([1,i]\) 的颜色相同贡献，\([l,r]\) 颜色相同的贡献等于 \(sum[r]-sum[l]\)。
方程变为：
\[dp[i][0][0]=\max_{j<i}(dp[j][1][0]-sum[j]+(a[j-1]==a[j])\times a[i])+sum[i-1] \]\[dp[i][0][1]=\max_{j\leq i}(dp[j][0][0]-sum[j])+sum[i] \]剩下两条与上面方程类似，就不写了。
对于方程 \(dp[i][0][1]\)，\(dp[j][0][0]-sum[j]\) 中取一个最大值可以 \(O(1)\) 的实现，对于另一个，发现难点在于 \(a[j-1]\) 与 \(a[i]\) 颜色相同时会产生一个 \(a[i]\) 的贡献。
那么先对于所有的 \(j\) 都不加 \(a[j-1]\) 与 \(a[i]\) 的贡献求一个 \(dp[j][1][0]-sum[j]\) 的最大值，同时在 \(a[j-1]\) 与 \(a[i]\) 相同的 \(j\) 里也求一个 \(dp[j][1][0]-sum[j]\) 的最大值，最后将后一个的最大值加 \(a[i]\) 与前一个最大值比较，便可以得出 \(dp[i][0][0]\) 的最终答案。
最后答案时 \(\max(dp[n][0][1],dp[n][1][1])\)。
Ps：其实你发现第 3 维的作用仅限于统计答案，所以其实可以去掉。
具体操作看实现，时间复杂度 \(O(n)\)。
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxL=1e6+5,maxn=2e5+5;
int n;
int a[maxn];
ll cho[maxL][2],acl[2],sum[maxn],dp[maxn][2][2];
int main()
{
// freopen("color2.in","r",stdin);
// freopen("color.out","w",stdout);
int _;
scanf("%d",&_);
while(_--)
{
memset(cho,-0x3f,sizeof(cho));
memset(acl,0,sizeof(acl));
memset(sum,0,sizeof(sum));
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(a[i-1]==a[i])*a[i];
for(int i=1;i<=n;i++)
{
dp[i][0][0]=max(acl[1]+sum[i-1],cho[a[i]][1]+sum[i-1]+a[i]);
dp[i][1][0]=max(acl[0]+sum[i-1],cho[a[i]][0]+sum[i-1]+a[i]);
acl[0]=max(acl[0],dp[i][0][0]-sum[i]);
acl[1]=max(acl[1],dp[i][1][0]-sum[i]);
cho[a[i-1]][1]=max(cho[a[i-1]][1],dp[i][1][0]-sum[i]);
cho[a[i-1]][0]=max(cho[a[i-1]][0],dp[i][0][0]-sum[i]);
dp[i][0][1]=acl[0]+sum[i];
dp[i][1][1]=acl[1]+sum[i];
}
printf("%lld\n",max(dp[n][0][1],dp[n][1][1]));
}
}
后记
去年忘记加 1 少 \(100pts\)，今年忘记 \(-1\) 少 \(50pts\)……
标签：颜色,P11233,max,sum,2024,int,最大值,CSP,dp From： https://www.cnblogs.com/binbin200811/p/18508887