链接
一群人在山上遇见了一条蜈蚣
在一条山路的转角处，WYH发现了一条有中指一样粗的有N节的蜈蚣。这只蜈蚣马上就吸引了HKE的眼球，HKE深深地爱上了这条魔性的蜈蚣。它的很多对足在前进的时候像波浪一样，颇是有毒。
但是，热爱解剖动物的MZL却准备把蜈蚣切了。HKE很失落，于是MZL承诺不会完全肢解它，只把它的N节切成M段，每一段包含原蜈蚣完整的一节或多节。
HKE看到他心爱的蜈蚣会切掉是会觉得恶心的。蜈蚣的每一节都有一个权值W[i]，切下来的一段(W[i],W[i+1],…,W[j])带给HKE的恶心值是W[i] xor W[i+1] xor … xor W[j]，这里的xor代表按位异或操作。邪恶的LJC希望HKE受到的总恶心值——也就是每一段子蜈蚣带给HKE的恶心值的和最大，请你求出HKE的最大恶心值。
（注：按位异或，其运算符号在pascal中为xor，在c++中为^或xor；请注意加法与异或运算的优先级先后顺序）
第一行，两个整数N,M，表示蜈蚣长N节，切成M段。
第二行N个整数用空格分开，表示蜈蚣每一节的权值W[1],W[2],…,W[n]。
一个整数表示最大恶心值。
第一段的恶心值为 1 xor 2 = 3
第二段的恶心值为 3 xor 4 = 7
第三段的恶心值为 5
总恶心值为 3+7+5=15。此时为最优解。
对于30%的数据，1≤N≤100,1≤M≤10；
对于100%的数据，1≤N≤1000,1≤M≤100，保证结果在2^30-1内；
首先，如果我们假设我们可以用O(1)的时间复杂度求得a[i] xor a[i+1] xor … a[j]（区间xor）,那么这就是一道水题
令dp[i][j]表示前i节，切成j段的最大恶心值
那么我们枚举在哪里切(k)，则dp[i][j]=max(dp[i][j],dp[k][j-1]+…) 其中的…就是我们之前说的区间xor（k xor 到 i）
现在我们来解决这个问题
引理1：a xor a=0 证明：由xor的定义，比较每一位，相同则为0，反之为1 两个相同的数的每一位肯定也是相同的，即每一位xor后为0，所以最终为0 得证
引理2：a xor 0=a 证明：考虑a的每一位：
若这一位为1：1 xor 0=1 若这一位为0：0 xor 0=0
也就是每一位异或后都相等，所以原数经过xor 0 后仍然等于原数
现在我们来推一推
假设s[i]=a[1] xor a[2] xor a[3] … a[i] s[j]=a[1] xor a[2] xor a[3] … a[j] (j<i)
我们来看看s[i]^s[j]会发生什么？
首先，红框框住的部分全部xor后为0（引理1）
然后，0和后面剩下的xor后就只剩下后面啦（引理2）
所以最终，s[i]^s[j]就等于a[j] xor a[j+1] xor a[j+2] xor… xor a[i]
那么我们就可以用类似于前缀和的方式求出任意一段的xor 啦
#include<cstdio> #include<iostream> using namespace std; const int MAXN=1005; const int MAXM=105; int dp[MAXN][MAXM]; int a[MAXN]; int s[MAXN]; int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); s[i]=s[i-1]^a[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; }