首先我们得知道什么是异或，这道题的核心就在于看到异或进行转移。
异或xor,^，A xor B就是再A,B两个数的二进制数中相同为0，不同为1。 一些定理： 0 x o r A = A ; 0 xor A = A; 0xorA=A; A x o r A = 0 ; A xor A = 0; AxorA=0; A x o r ( B x o r C ) = ( A x o r B ) x o r C ; A xor (B xor C) = (A xor B) xor C; Axor(BxorC)=(AxorB)xorC; 因为这道题是的蜈蚣是一节一节的，并且是要求蜈蚣分为m段再异或后的最大值，不难想到设Dp[i][j]表示前i节蜈蚣分为j段能获得的最大值。让后我们可以利用xor的交换律对这个进行转移。 d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i ] [ k ] + S u m X o r ( i , k ) ) dp[i][j] = max(dp[i][j],dp[i][k] + SumXor(i,k)) dp[i][j]=max(dp[i][j],dp[i][k]+SumXor(i,k)) 其中SumXor表示从i到k所有值异或起来的总和，我们可以设一个前缀和来表示前i个的异或总值，让后面DP时不用再一个一个地去求，以防T掉。dp的初始状态是dp[i][1] = sum[i],因为dp[i][1]就表示了i段分为1组的最大值，显然是他异或起来的本身，因为我们要求n段分为m组的最大值，所以说答案存在是dp[n][m]. 十分简洁的的代码：
#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 1e3 + 5; int n,m,w[MAXN],s[MAXN],dp[MAXN][MAXN]; int main() { scanf("%d %d",&n,&m); for(int i = 1;i <= n;i ++) { scanf("%d",&w[i]); s[i] = s[i - 1] ^ w[i]; } for(int i = 1;i <= n;i ++) dp[i][1] = s[i]; for(int j = 2;j <= m;j ++) for(int k = 1;k <= n;k ++) for(int i = k;i <= n;i ++) dp[i][j] = max(dp[i][j],dp[k][j - 1] + (s[i] ^ s[k])); printf("%d",dp[n][m]); return 0; }END
