CF2003F Turtle and Three Sequences 题解 / 随机化

题目传送门：CF2003F Turtle and Three Sequences。

首先如果 \(b\) 的值域很小我们就可以考虑状压，考虑对 \(b\) 的值域的每一个数染上一个 \([0,m-1]\) 的值，这样 \(b_i = b_j\) 映射后一定也满足，但是 \(b_i \neq b_j\) 不一定映射后满足，说明这个随机化求出的答案一定合法但不一定最优。

我们考虑随机 \(T\) 次来计算概率，一次成功的概率显然为 \(\frac{5!}{5^5} = 3.84\%\)，那么 \(T\) 次成功的概率显然为 \(1-(1-3.84\%)^T\)，取 \(T=100\) 几乎就是 \(100\%\)。

考虑如何计算答案，设 \(f_{i,j,S}\) 表示前 \(i\) 个位置，最后选择的一个位置的 \(a\) 值为 \(j\) 且选择的 \(b\) 的状态为 \(S\)。

\[f_{i,a_i,S} = \max_{k\le a_i,w_{b_i}\in S} \{f_{i-1,k,S \backslash {w_{b_i}}} + c_i\} \]

利用滚动数组和树状数组优化一下即可，复杂度 \(O(Tn2^m\log n)\)。

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
inline int read(){
	char c=getchar();
	int f=1,ans=0;
	while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
	while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
	return ans*f;
}
const int N=3010,M=1<<5;
mt19937_64 randd(time(0));
int n,m,a[N],b[N],c[N],w[N],f[M];
struct tree{
	int c[N];
	#define lowbit(x) x&-x
	inline void add(int i,int x){for (;i<=n;i+=lowbit(i)) c[i]=max(c[i],x);}
	inline int sum(int i){int ans=-1e18;for (;i;i-=lowbit(i)) ans=max(ans,c[i]);return ans;}
}t[M];
inline int solve(){
	for (int i=1;i<=n;i++) w[i]=randd()%m;
	for (int i=0;i<(1<<m);i++) for (int j=1;j<=n;j++) t[i].c[j]=-1e18;
	int ans=-1e18;
	for (int i=1;i<=n;i++){
		for (int j=0;j<(1<<m);j++) f[j]=-1e18;
		f[1<<w[b[i]]]=c[i];
		for (int j=0;j<(1<<m);j++) if ((j>>w[b[i]])&1) f[j]=max(f[j],t[j^(1<<w[b[i]])].sum(a[i])+c[i]);
		for (int j=0;j<(1<<m);j++) t[j].add(a[i],f[j]);
		ans=max(ans,f[(1<<m)-1]);
	}
	return ans;
}
main(){
	n=read(),m=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<=n;i++) b[i]=read();
	for (int i=1;i<=n;i++) c[i]=read();
	int T=100,ans=-1e18;
	while(T--) ans=max(ans,solve());
	if (ans<=0) puts("-1"); 
	else cout <<ans;
    return 0;
}