TCO12 1C 1000pt : FoxAndPhotography

問題概要

長さN(<=16)の数列a,bがある。a,b内でそれぞれ隣接する項をスワップすることを繰り返してa[i]

解法

まだよく理解していないのだけど、動かすのは片方の列だけだと考えて大丈夫らしい。
それを踏まえると、(前の列の何番目までは対応付けた、既に動かした後列の集合）を状態としてdpで計算できる。

acceptされたコード

計算量O(N^2*2^N)。

#include <cstring>
#include <vector>
using namespace std;

const int MAX_N = 16;
const int INF = 1<<29;

int N;
int hs[MAX_N], bs[MAX_N];
int memo[MAX_N][1<<MAX_N];
bool visited[MAX_N][1<<MAX_N];

struct FoxAndPhotography {

	int getMinimumSwaps(vector<int> hs_, vector<int> bs_) {
		N = hs_.size();
		for(int i=0; i<N; ++i){
			hs[i] = hs_[i];
			bs[i] = bs_[i];
		}
		int ans = rec(0, 0);
		return ans == INF ? -1 : ans;
	}

	int rec(int p, int bit){
		if(p == N){
			return 0;
		}
		if(visited[p][bit]){
			return memo[p][bit];
		}
		visited[p][bit] = true;

		int& ans = memo[p][bit] = INF;
		for(int i=0, t=0; i<N; ++i)if(!((bit>>i)&1)){
			if(hs[p] < bs[i]){
				ans = min(ans, t + rec(p+1, bit | (1<<i)));
			}
			++t;
		}

		return ans;
	}

};