序列划分

前言

  • 没想到我用dpA了它

分析

  • 从暴力入手,设 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;
}