Brief description:

Round 1B 1000. FoxAndPhotography:
。。两排长度为 n 的同学，问最少的交换次数，使得后排每位同学都不被前排同学遮住。
（。。交换限制在同排相邻位置进行。。n ≤ 16。。。）

Analysis:

。看到 n ≤ 16 怎么也该有点想法了。。。。我这也弱暴。。主要是没认识到子问题的独立性吧
。。。。。（。逆序对啊逆序对。。）。

（最后 250 脑残错误。。。然后手贱硬是把分数 cha 到 600 人以下。。）

const int N = 16;

int F[1<<16], n;

int w(int s, int i){
    int res = 0; FOR(j, i+1, n) if (_1(s, j)) ++res;
    return res;
}

class FoxAndPhotography {
public:
	int getMinimumSwaps(vector <int> A, vector <int> B) {

        n = SZ(A), FLC(F, 0x7f), F[0] = 0;

        REP(s, _U(n)) REP(i, n) if (!_1(s, i) && A[count_bits(s)] < B[i]){
            checkMin(F[s | _1(i)], F[s] + w(s, i));
        }

		return F[_U(n)] >= INF ? -1 : F[_U(n)];
	}
};

Posted by xiaodao
Category: TopCoder