序列划分
前言
分析
- 从暴力入手,设 f [ i ] 表示划分前i个数的最大价值,通过枚举区间 [ 1 , i - 1 ] 进行转移。但是,似乎n有点大,阿巴QwQ。
- 优化:按位异或,二进制位上,相同取0,不同取1,也就是说,任意多个数再怎么异或,得到的结果的位数(二进制)和其中最大的数的位数(二进制)是相同的。通过这个,我就可以大致判断出我最多需要枚举的个数而不是如同暴力一样从1开始枚举。于是我尝试对于每一个i,仅枚举十个数,结果给过了。但似乎正解其实就是输出和。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n;
ll a[N],f[N];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
for (int i=1;i<=n;i++)
{
ll now=a[i];f[i]=f[i-1]+a[i];
for (int j=i-1;j>=1;j--)
{
if(i-j>10) break;
now^=a[j];
f[i]=max(f[i],f[j-1]+now);
}
}
printf("%lld\n",f[n]);
return 0;
}