牛客挑战赛43 A-序列划分

序列划分

前言

• 没想到我用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;
}