自动搬运

查看原文

来自洛谷，原作者为

	Del_Your_Heart I've already lost what I ever had.It's time to say goodbye.AFO.

搬运于2025-08-24 22:07:36，当前版本为作者最后更新于2019-08-18 11:10:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

珂能更好的阅读体验(?)

题目大意：

给你一段长度为$n$的数组，让你分成$m$段，使其每段的异或和的总和最大。

区间$DP$

很明显，这题是一个区间$DP$的题，因为它满足区间DP的性质： 珂以由小的区间最优解得到更大的区间最优解（满足区间可合并性）

区间$DP$一般分为三个部分：

$1^o$ 状态：

对于本题，状态为区间起点，区间终点和分段次数。为了方便起见，我设置的状态为 $f[i][j]$ 表示从 $1-i$ 这段区间分为 $j$ 段所能得到的最大异或和。

有的人可能会质疑本蒟蒻：为什么不设置区间起点呢？

其实我一开始的状态为 $f[i][j][k]$ 表示从 $i-j$ 这段区间分为 $k$ 段所能得到的最大异或和，然鹅最后放弃了。

原因有两点：1.空间复杂度高，空间效率低下；2.状态转移方程不好写，思维难度大。 所以说，选择好的状态珂以提高程序效率，降低思维难度，使代码简洁易懂易调试，不易写挂。(像我这样的蒟蒻，写稍长一点的代码就调到自闭，心态炸裂)

$2^o$ 状态转移方程：

既然我们已经确定了状态，就让我们来简单地(话说真的十分简单)推一下状态转移方程。

考虑用靠前的区间去更新靠后的区间，我们有

$f[j][c+1]=max(f[j][c+1],f[i][c]+(sum[j]$ $xor$ $sum[i]))$

其中

$sum[i]=a[1]$ $xor$ $a[2]$ $xor$ …… $xor$ $a[i]$，$c$为区间个数

时间复杂度为$O(n^2*m)$，对于$n<=1000,m<=100$的数据珂以完美过掉

$3^o$ 初始化与边界条件：

显而易见的有$f[i][1]=sum[i]$。

而边界条件也很显然：$i,j \in [1,n],c \in [1,m]$

到这里我们已经珂以尝试写出完整代码了：

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1005][105],sum[1005];
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)){
        f|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+(ch^48);
        ch=getchar();
    }
    return f?-x:x;
}//快读
int main(){
    n=read();m=read();
    for(register int *i=sum+1;i<=sum+n;++i)
        *i=read()^*(i-1);//读入，处理前缀异或
    for(register int i=1;i<=n;++i)
        f[i][1]=sum[i];//初始化
    for(register int c=1;c<=m;++c)
        for(register int i=1;i<=n;++i)
            for(register int j=i;j<=n;++j)
                f[j][c+1]=max(f[j][c+1],f[i][c]+(sum[j]^sum[i]));//更新区间
    cout<<f[n][m];
    return 0;
}//手打一遍过，不用调来调去，真爽