题目链接:http://codeforces.com/contest/193/problem/B
题意:一个数列有两种操作,问操作u次后最大是权值和是多少。
操作1:ai ^ bi
操作2:ai = api + r
这题爆搜会TLE,但是有一个很明显的剪枝就是同时异或的话值是一样的。所以用一个pre记录上一步是不是异或。
仅仅这样会wa,因为事实上的确会存在有两次连续异或,并且最终更新到u的情况。那么需要在剩余操作次数为偶数次的时候都要更新答案,因为要考虑异或成对出现的情况。
1 #include2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 333; 6 int n, u, r; 7 LL a[maxn], b[maxn], k[maxn], p[maxn]; 8 LL ret; 9 vector path;10 11 void dfs(int cnt, bool pre) {12 if(cnt == u + 1) return;13 if((u - cnt) % 2 == 0) {14 LL tmp = 0;15 for(int i = 1; i <= n; i++) tmp += a[i] * k[i];16 ret = max(ret, tmp);17 }18 19 if(!pre) {20 for(int i = 1; i <= n; i++) a[i] ^= b[i];21 dfs(cnt+1, 1);22 for(int i = 1; i <= n; i++) a[i] ^= b[i];23 }24 25 LL t[maxn];26 for(int i = 1; i <= n; i++) t[i] = a[i];27 for(int i = 1; i <= n; i++) a[i] = t[p[i]] + r;28 dfs(cnt+1, 0);29 for(int i = 1; i <= n; i++) a[i] = t[i];30 }31 32 int main() {33 // freopen("in", "r", stdin);34 while(~scanf("%d%d%d",&n,&u,&r)) {35 for(int i = 1; i <= n; i++) scanf("%I64d",&a[i]);36 for(int i = 1; i <= n; i++) scanf("%I64d",&b[i]);37 for(int i = 1; i <= n; i++) scanf("%I64d",&k[i]);38 for(int i = 1; i <= n; i++) scanf("%I64d",&p[i]);39 ret = -1e18; path.clear();40 dfs(0, 0);41 printf("%I64d\n", ret);42 }43 return 0;44 }