http://apps.topcoder.com/wiki/display/tc/SRM+513
简化问题，x轴的移动对y轴z轴无影响，同样y轴z轴的移动对其它两个轴也是无影响的。所以问题的解就化简成三个子问题x轴上移动的最少步数、y轴上移动的最少步数和z轴上移动的最小步数之和。
分析可以看出点y通过位置为T的镜子可以到达的位置y1=2T-y，不论是从左边折越到右边或者从右边折越到左边。
可以证明如果最优解需要使用若干个镜子以及移动若干步，那么先使用镜子和先移动都是等价的。所以我们可以先考虑使用镜子，最后再一次性移动到目标位置。
假设使用若干面镜子，那么使用完后所在的位置肯定是：
2A
2A - 2B
2A - 2B + 2C
2A - 2B + 2C - 2D
...
A,B,C,D为镜子所在的位置，可以看出对于一面镜子来说，它可以不使用或者加上其位置的2倍或者减去其位置的2倍。假设做加法的镜子数为a，做减法的镜子数为s。那么 a == s 或者 a + 1 == s。
分析到这里程序只需要枚举每个镜子的使用状态即可。然而对于每个轴，镜子数最多为20。暴力枚举时间复杂度为O(3^N)，显然会超时。这里要使用到一个方法 meet-in-the-middle 。首先将镜子平均分成2部分，然后分别计算出两部分中的所有组合情况。最后枚举第一部分的组合情况，然后在第二部分中二分查找最接近的解，这样时间复杂度就降到了O(3^(N/2))。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>#define ll long longusing namespace std;int pow3[11];
vector<ll> A[11][21], B[11][21];class Reflections {
public:void makeMoves(vector<int> M, int s, int t, vector<ll> R[11][21]) {int n = t - s;int i, j, k, u, f;ll v;for (i = 0; i <= n; i++)for (j = 10 - i; j <= 10 + i; j++)R[i][j].clear();pow3[0] = 1;for (i = 1; i <= n; i++)pow3[i] = pow3[i-1] * 3;for (i = 0; i < pow3[n]; i++) {k = i; u = f = 0; v = 0;for (j = 0; k; j++, k /= 3) {switch (t % 3) {case 0: break;case 1: v += M[j+s] + M[j+s]; u++; f++; break;case 2: v -= M[j+s] + M[j+s]; u++; f--; break;}}R[u][f+10].push_back(v);}for (i = 0; i <= n; i++)for (j = 10 - i; j <= 10 + i; j++)sort(R[i][j].begin(), R[i][j].end());}ll binarySearch(vector<ll> &V, ll num) {int l = 0, r = V.size(), m;while (l < r) {m = (l + r) / 2;if (labs(num - V[m]) < labs(num - V[m+1]))r = m;elsel = m + 1;}return V[l];}ll minMove(vector<int> M, int P) {int n = M.size() / 2;int m = M.size() - n;makeMoves(M, 0, n, A);makeMoves(M, n, M.size(), B);ll res = labs(P);ll numA, numB;int ia, ib, ka, ja, jb;for (ia = 0; ia < n; ia++) {for (ja = 10 - ia; ja <= 10 + ia; ja++) {for (ib = 0; ib < m; ib++) {jb = 20 - ja;if (10 - ib <= jb && jb <= 10 + ib) {for (ka = 0; ka < A[ia][ja].size(); ka++) {numA = A[ia][ja][ka];numB = binarySearch(B[ib][jb], P - numA);if (res > abs(numA + numB - P) + ia + ib)res = abs(numA + numB - P) + ia + ib;}}jb = 21 - ja;if (10 - ib <= jb && jb <= 10 + ib) {for (ka = 0; ka < A[ia][ja].size(); ka++) {numA = A[ia][ja][ka];numB = binarySearch(B[ib][jb], P - numA);if (res > abs(numA + numB - P) + ia + ib)res = abs(numA + numB - P) + ia + ib;}}}}}return res;}ll minimumMoves(vector<int> X, vector<int> Y, vector<int> Z, vector<int> P) {return minMove(X, P[0]) + minMove(Y, P[1]) + minMove(Z, P[2]);}
};