学步园

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 long

using 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;
            else
                l = 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]);
    }
};