題目
鏈接
題目背景
一群人在山上遇見了一條蜈蚣
題目描述
在一條山路的轉角處，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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/162788.html
標籤：java