P5144题解

· · 题解

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

题目大意：

给你一段长度为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]))

其中

时间复杂度为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;
}//手打一遍过，不用调来调去，真爽