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; }