UVa-10037, ZOJ-1877, POJ-2573, TJU-1353 : Bridge

問題概要

人がN(<1000)人こちら側にいる。橋を渡って全員あちら側に渡りたい。橋は1度に二人しか通れない。橋を渡るにはライトが要る。ライトは一本しかない。各人には橋を渡るのにかかる時間が設定されていて、二人で渡るときは遅い方の時間がかかる。橋を渡るのにかかる最小の時間を求め、その手順を復元する問題。

考えたこと

速い順にソートする。1番速い人と2番目に速い人の位置とライトの位置とそれ以外の人が何人残っているか、という4つの組を状態としてメモ化再帰する。3番目以降の人の動かし方は、遅い方から動かしていけば良い。

acceptされたコード

計算量O(N)。ただし係数が大きい。そしてコード汚い…。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 1000;
const int INF = 1<<29;
const pair<int,int> END(-1,-1);

int N;
int costs[MAX_N];
int memo[2][2][2][MAX_N];
bool visited[2][2][2][MAX_N];
pair<int,int> next[2][2][2][MAX_N];

pair< pair<int,int>, pair<int,int> > next2[2][2][2][MAX_N];

void init(){
	memset(visited, false, sizeof(visited));

	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", costs+i);
	}

	sort(costs, costs+N);
}

//0:こちら側 1:あちら側
int dfs(int light, int f, int s, int ed){
	//メモ化処理
	if(visited[light][f][s][ed]){
		return memo[light][f][s][ed];
	}
	visited[light][f][s][ed] = true;

	int& ret = memo[light][f][s][ed];
	ret = INF;

	//基底
	if(light && f && s && ed<=1){
		next[light][f][s][ed] = END;
		return ret = 0;
	}

	//こちら->あちら
	if(!light){
		//一番遅い人を動かす
		if(ed >= 2){
			if(!f){
				int t = costs[ed] + dfs(1-light, 1-f, s, ed-1);
				if(t < ret){
					ret = t;
					next[light][f][s][ed] = make_pair(costs[0], costs[ed]);
					next2[light][f][s][ed] = make_pair( make_pair(1-light, 1-f), make_pair(s, ed-1) );
				}
			}
			if(!s){
				int t = costs[ed] + dfs(1-light, f, 1-s, ed-1);
				if(t < ret){
					ret = t;
					next[light][f][s][ed] = make_pair(costs[1], costs[ed]);
					next2[light][f][s][ed] = make_pair( make_pair(1-light, f), make_pair(1-s, ed-1) );
				}
			}
			{
				int t = costs[ed] + dfs(1-light, f, s, ed-1);
				if(t < ret){
					ret = t;
					next[light][f][s][ed] = make_pair(costs[ed], -1);
					next2[light][f][s][ed] = make_pair( make_pair(1-light, f), make_pair(s, ed-1) );
				}
			}
		}
		//遅い奴を二人動かす
		if(ed >= 3){
			int t = costs[ed] + dfs(1-light, f, s, ed-2);
			if(t < ret){
				ret = t;
				next[light][f][s][ed] = make_pair(costs[ed-1], costs[ed]);
				next2[light][f][s][ed] = make_pair( make_pair(1-light, f), make_pair(s, ed-2) );
			}
		}
		//速い奴を動かす
		if(!f){
			int t = costs[0] + dfs(1-light, 1-f, s, ed);
			if(t < ret){
				ret = t;
				next[light][f][s][ed] = make_pair(costs[0], -1);
				next2[light][f][s][ed] = make_pair( make_pair(1-light, 1-f), make_pair(s, ed) );
			}
		}
		if(!s){
			int t = costs[1] + dfs(1-light, f, 1-s, ed);
			if(t < ret){
				ret = t;
				next[light][f][s][ed] = make_pair(costs[1], -1);
				next2[light][f][s][ed] = make_pair( make_pair(1-light, f), make_pair(1-s, ed) );
			}
		}
		if(!f && !s){
			int t = costs[1] + dfs(1-light, 1-f, 1-s, ed);
			if(t < ret){
				ret = t;
				next[light][f][s][ed] = make_pair(costs[0], costs[1]);
				next2[light][f][s][ed] = make_pair( make_pair(1-light, 1-f), make_pair(1-s, ed) );
			}
		}
	}
	//あちら->こちら
	else{
		if(f){
			int t = costs[0] + dfs(1-light, 1-f, s, ed);
			if(t < ret){
				ret = t;
				next[light][f][s][ed] = make_pair(costs[0], -1);
				next2[light][f][s][ed] = make_pair( make_pair(1-light, 1-f), make_pair(s, ed) );
			}
		}
		if(s){
			int t = costs[1] + dfs(1-light, f, 1-s, ed);
			if(t < ret){
				ret = t;
				next[light][f][s][ed] = make_pair(costs[1], -1);
				next2[light][f][s][ed] = make_pair( make_pair(1-light, f), make_pair(1-s, ed) );
			}
		}
		if(f && s){
			int t = costs[1] + dfs(1-light, 1-f, 1-s, ed);
			if(t < ret){
				ret = t;
				next[light][f][s][ed] = make_pair(costs[0], costs[1]);
				next2[light][f][s][ed] = make_pair( make_pair(1-light, 1-f), make_pair(1-s, ed) );
			}
		}
	}

	return ret;
}

void solve(){
	if(N == 1){
		printf("%d\n%d\n", costs[0], costs[0]);
		return ;
	}
	else if(N==2){
		printf("%d\n%d %d\n", costs[1], costs[0], costs[1]);
		return ;
	}
	printf("%d\n", dfs(0,0,0,N-1));
	int l = 0, f = 0, s = 0, ed = N-1;
	while(next[l][f][s][ed] != END){
		pair<int,int> move = next[l][f][s][ed];
		if(move.second == -1){
			printf("%d\n", move.first);
		}
		else{
			printf("%d %d\n", move.first, move.second);
		}
		pair< pair<int,int>, pair<int,int> > tar = next2[l][f][s][ed];
		l = tar.first.first;
		f = tar.first.second;
		s = tar.second.first;
		ed = tar.second.second;
	}
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		init();
		solve();
		if(T){
			puts("");
		}
	}
	return 0;
}