|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
题意大致是：在三维空间中，从原点走到(x,y,z)，每次可以向六个方向中的一个方向走一步，或者沿一面镜子对称，问至少行动多少次可以到达终点。
每面镜子都是垂直于x轴、y轴、z轴中的一条轴的平面，且垂直于一条轴的镜子数最多为20。每面镜子最多被用来对称一次。
题解：
代码来自TopCoder Wiki。
若直接进行移动，则只会改变三维中的一维，做对称也一样，所以三维可以分开讨论。
因为镜像操作只是进行对称，所以直接移动可以放在最后进行。这样，我们只要搜索按哪种顺序选用了哪些镜子，将得到的坐标与终点做差，即为在这个维度直接移动的次数。
直接枚举显然会超时，我们可以考虑优化。
考虑垂直于x轴的镜子的操作：若点坐标为a，镜子坐标为b，则对称后点坐标为2*b-a。
经过一系列对称，最终点坐标展开为（2*b[n]-2*b[n-1]+2*[b-2]-......-2*b[2]+2*b[1]-a）或（2*b[n]-2*b[n-1]+2*[b-2]-......+2*b[2]-2*b[1]+a）。
即某面被选用镜子操作的贡献只与选用顺序序号的奇偶性有关。
可以枚举n面奇数序号的镜子与n面偶数序号的镜子，原坐标贡献为正；或枚举n面奇数序号的镜子与n+1面偶数序号的镜子，原坐标贡献为负。
可是这样枚举依旧会TLE。
我们可以采用折半搜索，就不会TLE了，可是十分不好写。
事实上，我们可以分别枚举奇数序号镜子的集合与偶数序号镜子的集合，而不用考虑重复的情况。对于重复的情况，可以看做是一面镜子用了两次（效果等同于不使用），可以正常处理，但一定不是最优解。
枚举好后，用类似于折半搜索的做法合并即可。
代码：
class Reflections
{
public:
long long solve(vector<int>& M, int P)
{
int N = M.size();
// Compute the sum of each subset.
vector<long long> V[];
for(int i = ; i < << N; i++)
{
long long sum = ;
for(int j = ; j < N; j++) if(i & << j) sum += M[j] * 2ll;
V[__builtin_popcount(i)].push_back(sum);
}
// For each subset find the subset of the same or one lesser size that puts us closest to our target.
long long ret = abs(P);
for(int i = ; i <= (N + ) / ; i++)
{
sort(V[i].begin(), V[i].end());
for(int j = ; j < V[i].size(); j++)
{
// Find subsets of equal size that put us close to P.
int pos = upper_bound(V[i].begin(), V[i].end(), V[i][j] - P) - V[i].begin();
if(pos < V[i].size()) ret = min(ret, * i + abs(P - V[i][j] + V[i][pos]));
if(pos > ) ret = min(ret, * i + abs(P - V[i][j] + V[i][pos - ])); // Find subsets of one lesser size that put us close to P.
if(!i) continue;
pos = upper_bound(V[i - ].begin(), V[i - ].end(), V[i][j] - P) - V[i - ].begin();
if(pos < V[i - ].size()) ret = min(ret, * i - + abs(P - V[i][j] + V[i - ][pos]));
if(pos > ) ret = min(ret, * i - + abs(P - V[i][j] + V[i - ][pos - ]));
}
}
return ret;
}
long long minimumMoves(vector<int> X, vector<int> Y, vector<int> Z, vector<int> P)
{
return solve(X, P[]) + solve(Y, P[]) + solve(Z, P[]);
}
};