lg7335 [JRKSJ R1] 异或题解

本题的标签中含有trie，但是这道题可以不用trie做。

考虑列出本题的dp方程：设\(f_{k,i}\)表示前\(i\)个数选了\(k\)段的答案，\(s_i\)为数组的前缀异或和

当不选择第\(i\)位，使用\(f_{k,i-1}\)更新\(f_{k,i}\)。当选择第\(i\)位时，枚举选择的区间的左端点\(j+1\)，使用\(f_{k-1,j}+s_j\ xor\ s_k\)更新\(f_{k,i}\)。

由于本题数据随机，考虑更为优秀的做法。枚举\(k,i\)，设\(a_j=s_j\ xor\ s_i\)，则\(a\)可以看做随机数列。

显然\(f_{k,1...n}\)单调递增，所以假设存在\(2\)个位置\(j<k\)且\(a_j<a_k\)，那么不用考虑\(j\)。

利用该性质，设\(g_{k}\)表示\(k\)左边的第一个大于\(a_k\)的点（不存在视为\(0\)），则对于\(f_{k,i}\)，可行的决策点为\(i,g_i,g_{g_i}...\)，即不断地执行\(i=g_i\)操作直到\(i=0\)所经过的非\(0\)点所构成的集合。

根据经典结论，这个集合的期望大小为\(\log_2n\)，所以此做法时间复杂度为\(O(n^2\log_2n)\)。

#include<bits/stdc++.h>

using namespace std;

#define N 3010

int g[N][N],n,k,a[N],s[N],tp[N],ans;

long long f[N][N];

int main(){

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i]);

		s[i]=s[i-1]^a[i];

		tp[i]=1;

		g[i][1]=i-1;

		for(int j=i-2;~j;j--){

			if((s[i]^s[j])>(s[i]^s[g[i][tp[i]]]))

				g[i][++tp[i]]=j;

		}

	}

	for(int k=1;k<=n;k++){

		for(int i=1;i<=n;i++){

			f[k][i]=max(f[k][i],f[k][i-1]);

			for(int j=1;j<=tp[i];j++)

				f[k][i]=max(f[k][i],f[k-1][g[i][j]]+(s[g[i][j]]^s[i]));

		}

	}

	printf("%lld",f[k][n]);

}

巴特西

lg7335 [JRKSJ R1] 异或题解

最新文章

热门文章

巴特西

lg7335 [JRKSJ R1] 异或 题解

最新文章

热门文章

lg7335 [JRKSJ R1] 异或题解