Codeforces Round #122 (Div. 1) B : Xor

問題概要

配列に、各要素にある値を加えて置換or各要素にある値をxorする作業をr(<30)回以下繰り返す。配列の重み付き和を最大化する問題。

解法

全探索する。ただしxorを2回繰り返すのは元に戻るだけなので探索しないようにする。こうすると計算量はF_30 * 長さくらいになって間に合う。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

typedef long long int64;

const int MAX_N = 30;

int N, R, U;
int as[MAX_N], bs[MAX_N], ps[MAX_N], ks[MAX_N];
int64 ans;

void init(){
	scanf("%d%d%d", &N, &U, &R);
	for(int i=0; i<N; ++i){
		scanf("%d", as+i);
	}
	for(int i=0; i<N; ++i){
		scanf("%d", bs+i);
	}
	for(int i=0; i<N; ++i){
		scanf("%d", ks+i);
	}
	for(int i=0; i<N; ++i){
		scanf("%d", ps+i);
		--ps[i];
	}
}

void dfs(int res, int prev){
	if( !(res&1) ){
		int64 tmp = 0;
		for(int i=0; i<N; ++i){
			tmp += (int64)as[i] * ks[i];
		}
		ans = max(ans, tmp);
		if(res == 0){
			return ;
		}
	}

	int tmp[MAX_N];
	memcpy(tmp, as, sizeof(as));
	if(!prev){
		for(int i=0; i<N; ++i){
			as[i] ^= bs[i];
		}
		dfs(res-1, 1);
		memcpy(as, tmp, sizeof(as));
	}
	for(int i=0; i<N; ++i){
		as[i] = tmp[ps[i]] + R;
	}
	dfs(res-1, 0);
	memcpy(as, tmp, sizeof(as));
}

int64 solve(){
	ans = -(1LL<<60);
	dfs(U, 0);
	return ans;
}

int main(){
	init();
	cout << solve() << endl;

	return 0;
}