P11233 [CSP-S 2024] 染色（官方数据）

标签：10 A1 leq P11233 2024 ai int A2 CSP

[CSP-S 2024] 染色（官方数据）

题目描述

给定一个长度为 n n n 的正整数数组 A A A，其中所有数从左至右排成一排。

你需要将 A A A 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：

设 C C C 为长度为 n n n 的整数数组，对于 A A A 中的每个数 A i A_i Ai​（ 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n）：

• 如果 A i A_i Ai​ 左侧没有与其同色的数，则令 C i = 0 C_i = 0 Ci​=0。
• 否则，记其左侧与其最靠近的同色数为 A j A_j Aj​，若 A i = A j A_i = A_j Ai​=Aj​，则令 C i = A i C_i = A_i Ci​=Ai​，否则令 C i = 0 C_i = 0 Ci​=0。

你的最终得分为 C C C 中所有整数的和，即 ∑ i = 1 n C i \sum \limits_{i=1}^n C_i i=1∑n​Ci​。你需要最大化最终得分，请求出最终得分的最大值。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 T T T，表示数据组数。

接下来包含 T T T 组数据，每组数据的格式如下：

第一行包含一个正整数 n n n，表示数组长度。

第二行包含 n n n 个正整数 A 1 , A 2 , … , A n A_1, A_2, \dots, A_n A1​,A2​,…,An​，表示数组 A A A 中的元素。

输出格式

对于每组数据：输出一行包含一个非负整数，表示最终得分的最大可能值。

样例 #1

样例输入 #1

3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4

样例输出 #1

1
0
8

提示

【样例 1 解释】

对于第一组数据，以下为三种可能的染色方案：

1. 将 A 1 , A 2 A_1, A_2 A1​,A2​ 染成红色，将 A 3 A_3 A3​ 染成蓝色（ 1 2 1 \red{1}\red{2}\blue{1} 121），其得分计算方式如下：

• 对于 A 1 A_1 A1​，由于其左侧没有红色的数，所以 C 1 = 0 C_1 = 0 C1​=0。
• 对于 A 2 A_2 A2​，其左侧与其最靠近的红色数为 A 1 A_1 A1​。由于 A 1 ≠ A 2 A_1 \neq A_2 A1​=A2​，所以 C 2 = 0 C_2 = 0 C2​=0。
• 对于 A 3 A_3 A3​，由于其左侧没有蓝色的数，所以 C 3 = 0 C_3 = 0 C3​=0。
  该方案最终得分为 C 1 + C 2 + C 3 = 0 C_1 + C_2 + C_3 = 0 C1​+C2​+C3​=0。

2. 将 A 1 , A 2 , A 3 A_1, A_2, A_3 A1​,A2​,A3​ 全部染成红色（ 121 \red{121} 121），其得分计算方式如下：

• 对于 A 1 A_1 A1​，由于其左侧没有红色的数，所以 C 1 = 0 C_1 = 0 C1​=0。
• 对于 A 2 A_2 A2​，其左侧与其最靠近的红色数为 A 1 A_1 A1​。由于 A 1 ≠ A 2 A_1 \neq A_2 A1​=A2​，所以 C 2 = 0 C_2 = 0 C2​=0。
• 对于 A 3 A_3 A3​，其左侧与其最靠近的红色数为 A 2 A_2 A2​。由于 A 2 ≠ A 3 A_2 \neq A_3 A2​=A3​，所以 C 3 = 0 C_3 = 0 C3​=0。
  该方案最终得分为 C 1 + C 2 + C 3 = 0 C_1 + C_2 + C_3 = 0 C1​+C2​+C3​=0。

3. 将 A 1 , A 3 A_1, A_3 A1​,A3​ 染成红色，将 A 2 A_2 A2​ 染成蓝色（ 1 2 1 \red{1}\blue{2}\red{1} 121），其得分计算方式如下：

• 对于 A 1 A_1 A1​，由于其左侧没有红色的数，所以 C 1 = 0 C_1 = 0 C1​=0。
• 对于 A 2 A_2 A2​，由于其左侧没有蓝色的数，所以 C 2 = 0 C_2 = 0 C2​=0。
• 对于 A 3 A_3 A3​，其左侧与其最靠近的红色数为 A 1 A_1 A1​。由于 A 1 = A 3 A_1 = A_3 A1​=A3​，所以 C 3 = A 3 = 1 C_3 = A_3 = 1 C3​=A3​=1。
  该方案最终得分为 C 1 + C 2 + C 3 = 1 C_1 + C_2 + C_3 = 1 C1​+C2​+C3​=1。

可以证明，没有染色方案使得最终得分大于 1 1 1。

对于第二组数据，可以证明，任何染色方案的最终得分都是 0 0 0。

对于第三组数据，一种最优的染色方案为将 A 1 , A 2 , A 4 , A 5 , A 7 A_1, A_2, A_4, A_5, A_7 A1​,A2​,A4​,A5​,A7​ 染为红色，将 A 3 , A 6 , A 8 A_3, A_6, A_8 A3​,A6​,A8​ 染为蓝色（ 35 2 51 2 1 4 \red{35}\blue{2}\red{51}\blue{2}\red{1}\blue{4} 35251214），其对应 C = [ 0 , 0 , 0 , 5 , 0 , 1 , 2 , 0 ] C = [0, 0, 0, 5, 0, 1, 2, 0] C=[0,0,0,5,0,1,2,0]，最终得分为 8 8 8。

【样例 2】

见选手目录下的 color/color2.in 与 color/color2.ans。

【数据范围】

对于所有测试数据，保证： 1 ≤ T ≤ 10 1\leq T\leq 10 1≤T≤10， 2 ≤ n ≤ 2 × 1 0 5 2\leq n\leq 2\times 10^5 2≤n≤2×105， 1 ≤ A i ≤ 1 0 6 1\leq A_i\leq 10^6 1≤Ai​≤106。

测试点	n n n	A i A_i Ai​
1 ∼ 4 1\sim 4 1∼4	≤ 15 \leq 15 ≤15	≤ 15 \leq 15 ≤15
5 ∼ 7 5\sim 7 5∼7	≤ 1 0 2 \leq 10^2 ≤102	≤ 1 0 2 \leq 10^2 ≤102
8 ∼ 10 8\sim 10 8∼10	≤ 2000 \leq 2000 ≤2000	≤ 2000 \leq 2000 ≤2000
11 , 12 11,12 11,12	≤ 2 × 1 0 4 \leq 2\times 10^4 ≤2×104	≤ 1 0 6 \leq 10^6 ≤106
13 ∼ 15 13\sim 15 13∼15	≤ 2 × 1 0 5 \leq 2\times 10^5 ≤2×105	≤ 10 \leq 10 ≤10
16 ∼ 20 16\sim 20 16∼20	≤ 2 × 1 0 5 \leq 2\times 10^5 ≤2×105	≤ 1 0 6 \leq 10^6 ≤106

提供一个代码实现非常简单十分简短的做法。

返璞归真，状态没必要设置那么复杂，设 fif_ifi​ 表示考虑到第 iii 位的答案。显然的，对于每一个位置 iii 可以令 fi=fi−1f_i = f_{i-1}fi​=fi−1​。

用 lstilst_ilsti​ 记录 iii 上一次出现的位置，初始化令所有的 lsti=0lst_i = 0lsti​=0，每遍历到一个位置，动态更新 lstai=ilst_{a_i} = ilstai​​=i。然后枚举区间更新 fif_ifi​，也可以预处理出来一个 ggg 数组辅助转移，复杂度 O(n2)O(n^2)O(n2)。

50pts code

使用前缀和优化，每当 ai=ai−1a_i=a_{i-1}ai​=ai−1​ 时，更新前缀和数组 sis_isi​。最后对于 aia_iai​ 如果 lstailst_{a_i}lstai​​ 存在，对于 fif_ifi​ 的转移为：

fi=max⁡i=1n{flstai+1+ai+si−slstai}f_i=\max_{i=1}^{n}\{f_{lst_{a_i}+1}+a_i+s_i-s_{lst_{a_i}}\}fi​=i=1maxn​{flstai​​+1​+ai​+si​−slstai​​​}

最终的答案为 fnf_nfn​。

复杂度 O(n)O(n)O(n)。

#include <bits/stdc++.h>
#define int long long
#define rint register int
#define endl '\n'
#define m(a) memset(a, 0, sizeof a)
using namespace std;
const int N = 1e6 + 5;
int n, T;
int a[N], lst[N], f[N];
int s[N], ans; 
signed main() 
{
	cin >> T;
	while (T--) 
	{
		cin >> n;
		m(a), m(lst), m(f), m(s);
		for (rint i = 1; i <= n; i++) cin >> a[i];
		for (rint i = 2; i <= n; i++) s[i] = (a[i] == a[i - 1] ? s[i - 1] + a[i] : s[i - 1]);
		for (rint i = 1; i <= n; i++) 
		{
			f[i] = f[i - 1];
			if (lst[a[i]]) f[i] = max(f[i], f[lst[a[i]] + 1] + a[i] + s[i] - s[lst[a[i]] + 1]);
			lst[a[i]] = i;
		}
		cout << f[n] << endl;
	} 
	return 0;
}

讲一个在考场上独到的解析思路：

思路

不妨设：

ai=aja_{i}=a_{j}ai​=aj​

发现：如果想让一个数有价值，就要将 aia_{i}ai​ 与 aja_{j}aj​ 置为一种颜色（假设为红），中间的颜色置为不同的颜色（假设为蓝）。样例：

那么我们更进一步：既然需要将中间的颜色置为同一种颜色，那我们可以将 i+1i+1i+1 位置与 j−1j-1j−1 位置连接一条边权为 aia_{i}ai​ 的边。

当不相交的边的权值和最大时，即为最优情况。我们以考场大样例第一个为例子。

较为特殊的情况：若 j=i+1j=i+1j=i+1，那么最优的情况一定是将 aia_{i}ai​ 与 aja_{j}aj​ 画为同一种颜色。

证明：若 aia_{i}ai​ 与 aja_{j}aj​ 不为同一种颜色，那么既会得不到 aja_{j}aj​ 的贡献，也不会得到某条跨过 aia_{i}ai​ 与 aja_{j}aj​ 的边权。相反，若 aia_{i}ai​ 与 aja_{j}aj​ 为同一种颜色，他们不会影响任何其他的值。

所以我们直接把 aia_{i}ai​ 加入答案 ansansans 中。 当我们只选择边权为 131313 的边时，结果最大。

求解

所以，怎么办呢？

设:

• tit_{i}ti​：数字 iii 上一次出现的位置。

• outiout_{i}outi​：以 iii 为终点的连边的起点。

• viv_{i}vi​：以 iii 为终点的连边的边权。

则有：

dpi=max⁡(dpi−1,dpouti−1+vi)dp_{i}=\max(dp_{i-1},dp_{out_{i}-1}+v_{i})dpi​=max(dpi−1​,dpouti​−1​+vi​)

解析：要么选择这条边，那么就从 outi−1out_{i}-1outi​−1 位置转移方程。因为这一段都不能选择，线不可以交叉。要么不选择，答案就是上一个点的值。

那么代码就非常容易啦：

code

#include <bits/stdc++.h>
using namespace std;
const int M=1e6+10,N=2e5+10;
typedef long long ll;
ll n,a[N],dp[N],out[N],t[M],ans=0,v[N],p;
int main(){
	cin>>p;
	for(int k=1;k<=p;k++){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(t[a[i]]){ //如果 a[i] 存在上一个数
				if(t[a[i]]==i-1){ //如果与上一个数挨着
					ans+=a[i]; //答案直接加上
				}else{
					out[i-1]=t[a[i]]+1;
              	//将i-1 与 上一个 a[i] 的后一个连边
					v[i-1]=a[i];//将边权设置为 a[i]
				}
			}
			t[a[i]]=i; //存下 a[i] 位置
		}
		for(int i=1;i<=n;i++){
			dp[i]=dp[i-1];
			if(out[i]) dp[i]=max(dp[i],dp[out[i]-1]+v[i]);
              // 状态转移
		}
		ans+=dp[n]; //加上特殊的答案
		cout<<ans<<'\n';
          //别忘了多组数据清空！我就因为这个T2寄了
		for(int i=1;i<=n;i++){
			t[a[i]]=0;
			a[i]=0;
			out[i]=0;
			v[i]=0;
			dp[i]=0;
		} 
		ans=0;
	}
}

时间复杂度：O(tn)O(tn)O(tn)

thanks！

标签：10,A1,leq,P11233,2024,ai,int,A2,CSP
From： https://blog.csdn.net/yaosichengalpha/article/details/143807586