【GDOI2017模拟二试4.12】石子游戏

本文主要是介绍【GDOI2017模拟二试4.12】石子游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

给出n个数a[i]，将x改为y的代价为|x-y|，求将a变成xor和为零的最小代价。
$1\le n\le 15,0\le a[i]\le 10^9$

题解

考虑动态规划，按二进制从高到低，用 $3^n$ 的状态表示每个数是在k位之前是增加/不变/减少，设f[k][i][S][0/1]表示当前做到第k位，当前考虑第i位，S为每个数的状态，然后转移有：
1、若k位之前是不变，那么当前可以转成增加/不变/减少
2、若k位之前是增加/减少，那么状态不变
时间复杂度是 $O(32\times n\times 3^n)$
然后是过不了的
考虑怎么把 $3^n$ 变成 $2^n$ ，就是说要把增加和减少归为同一类，对于一个数的减少，我们可以先把后面的位减成全部都为1，比如 $(10100)_2$ 可以减成 $(10011)_2$ ，然后对于增加，就把后面的位全都变成0，这样做的好处是，当我们在后面的位里如果把增加的数的0变为1或把减少的数的1变为0都会产生贡献
对于已经确定了增加/减少的数我们称之为“不自由的”
那么可以设f[k][i][s][x][y]表示从高到低，做到第k位，当前考虑第i个数，是否自由的状态为s，当前位的xor和为x，已经确定的不自由的位在后面的位中的xor和为y
转移要分几种情况：
若第i位是自由的，那么可以考虑让它保持自由
或者将它变得不自由：
1、如果当前第k位为1，那么就要减少，算上贡献就是(a[i]&(mi[k+1]-1))-(mi[k]-1)
2、如果当前第k位为0，那么就要增加，算上贡献就是mi[k]-(a[i]&(mi[k+1]-1))
若第i位不自由，可以不更改状态直接转
或者将当前位改变，那么贡献为mi[k]

需要注意的地方是，状态中的y表示的是所有不自由位置的xor和，就是说当前位的状态不会影响这个y

Code

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;typedef long long LL;
typedef double db;int get(){char ch;while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');if (ch=='-'){int s=0;while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';return -s;}int s=ch-'0';while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';return s;
}const int N = 16;
const int L = 33000;
const int W = 33;
const LL INF = 2e+10;
const int U = 31;LL f[2][N][L][2][2];//s:0 for free;1 for limited;
int T,n;
int a[N][W];
LL mi[W];
LL val[N];LL minll(LL x,LL y){if (x<y)return x;return y;
}int main(){freopen("stone.in","r",stdin);freopen("stone.out","w",stdout);T=get();mi[0]=1;fo(i,1,32)mi[i]=mi[i-1]<<1;while(T--){n=get();fo(i,1,n){int x=get();fd(u,31,0)if ((mi[u]&x)>0)a[i][u]=1;else a[i][u]=0;val[i]=x;}fo(u,0,1)fo(i,1,n)fo(s,0,mi[n]-1)fo(x,0,1)fo(y,0,1)f[u][i][s][x][y]=INF;int now=0;f[0][n][0][0][0]=0;fd(k,U,0){int t=now^1;fo(i,0,n)fo(s,0,mi[n]-1)fo(x,0,1)fo(y,0,1)f[t][i][s][x][y]=INF;fo(s,0,mi[n]-1)fo(x,0,1)f[t][0][s][x][x]=f[now][n][s][0][x];fo(i,1,n)fo(s,0,mi[n]-1){if ((mi[i-1]&s)==0){//free//still freefo(x,0,1)fo(y,0,1)f[t][i][s][x^a[i][k]][y]=minll(f[t][i][s][x^a[i][k]][y],f[t][i-1][s][x][y]);//set limitedif (a[i][k]){//-:set 1//f[t][i][s|mi[i-1]][x][y]  f[t][i-1][s][x][y]+(val[i]&(mi[k+1]-1))-(mi[k]-1)fo(x,0,1)fo(y,0,1)f[t][i][s|mi[i-1]][x][y^1]=minll(f[t][i][s|mi[i-1]][x][y^1],f[t][i-1][s][x][y]+(val[i]&(mi[k+1]-1))-(mi[k]-1));}else{//+;set 0fo(x,0,1)fo(y,0,1)f[t][i][s|mi[i-1]][x^1][y]=minll(f[t][i][s|mi[i-1]][x^1][y],f[t][i-1][s][x][y]+mi[k]-(val[i]&(mi[k+1]-1)));}}else{//stayfo(x,0,1)fo(y,0,1)f[t][i][s][x][y]=minll(f[t][i][s][x][y],f[t][i-1][s][x][y]);//transfo(x,0,1)fo(y,0,1)f[t][i][s][x^1][y]=minll(f[t][i][s][x^1][y],f[t][i-1][s][x][y]+mi[k]);}}now=t;}LL ans=INF;fo(s,0,mi[n]-1)fo(x,0,1)ans=minll(ans,f[now][n][s][0][x]);printf("%lld\n",ans);}fclose(stdin);fclose(stdout);return 0;
}