題目

連結

題目背景

一群人在山上遇見了一條蜈蚣

題目描述

在一條山路的轉角處，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]。

輸出格式

一個整數表示最大惡心值。

輸入輸出樣例

輸入

5 3
1 2 3 4 5

輸出

15

說明/提示

第一段的噁心值為 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;
}