题解：P7335 [JRKSJ R1] 异或
zhujianheng
·
·
题解
5pts：
直接爆搜。O(n^{2k})。
40pts：
发现可能可以 DP。记 f_{i,j} 为前 i 个数中选 j 个区间，则转移方程：
$f_{i,j}=f_{l-1,j-1}+w_{l,i}$。（选区间）
时间复杂度 $O(n^2k)$。
100pts：
我们定义一个区间是“无用的”，当且仅当存在另一个区间，使得这个区间比另一个区间长，且没有另一个区间异或和大。
我们将这些无用区间抛弃掉，剩下几个区间？考虑一个长度为 $1$ 的区间，必然是有用的。长度为 $2$ 的呢？因为数据随机，所以 $a_i$ 异或 $a_{i-1}$ 大于 $a_i$ 的概率是 $\dfrac{1}{2}$，同理，一个长度为 $len$ 的区间，是有用的概率为 $\dfrac{1}{len}$。
所以在剔除无效区间后再 DP。调和级数 $1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}$ 是 $O(\ln n)$ 的，所以时间复杂度 $O(nk \ln n)$。
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3009;
struct Node{
int l,r,w;
}s[N][N];
int n,k,V,x[N],num[N],mx[N][N];
ll f[N][2];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>x[i],x[i]=x[i-1]^x[i];
for(int i=1;i<=n;i++)
for(int j=i-1,tmp=0;j>=0;j--)
tmp=max(tmp,x[i]^x[j]),mx[j][i]=max(mx[j][i-1],tmp);
for(int i=1;i<=n;i++){
s[i][1].l=s[i][1].r=0;
s[i][1].w=mx[0][i];
num[i]=1;
for(int j=1;j<i;j++)
if(mx[j][i]==mx[j-1][i]) s[i][num[i]].r++;
else{
s[i][++num[i]].l=j;
s[i][num[i]].r=j;
s[i][num[i]].w=mx[j][i];
}
}
for(ll j=1;j<=k;j++)
for(ll i=1;i<=n;i++){
f[i][j%2]=0;
for(ll x=1;x<=num[i];x++)
f[i][j%2]=max(f[i][j%2],f[s[i][x].r][(j%2)^1]+s[i][x].w);
}
cout<<f[n][k%2]<<endl;
return 0;
}
```