POJ-3404, TJU-2440 : Bridge over a rough river

問題概要

Crossing Riverの類題

acceptされたコード

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

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

int N;
int costs[MAX_N];
int memo[2][2][2][MAX_N];
bool visited[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){
		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;
				}
			}
			if(!s){
				int t = costs[ed] + dfs(1-light, f, 1-s, ed-1);
				if(t < ret){
					ret = t;
				}
			}
			{
				int t = costs[ed] + dfs(1-light, f, s, ed-1);
				if(t < ret){
					ret = t;
				}
			}
		}
		//遅い奴を二人動かす
		if(ed >= 3){
			int t = costs[ed] + dfs(1-light, f, s, ed-2);
			if(t < ret){
				ret = t;
			}
		}
		//速い奴を動かす
		if(!f){
			int t = costs[0] + dfs(1-light, 1-f, s, ed);
			if(t < ret){
				ret = t;
			}
		}
		if(!s){
			int t = costs[1] + dfs(1-light, f, 1-s, ed);
			if(t < ret){
				ret = t;
			}
		}
		if(!f && !s){
			int t = costs[1] + dfs(1-light, 1-f, 1-s, ed);
			if(t < ret){
				ret = t;
			}
		}
	}
	//あちら->こちら
	else{
		if(f){
			int t = costs[0] + dfs(1-light, 1-f, s, ed);
			if(t < ret){
				ret = t;
			}
		}
		if(s){
			int t = costs[1] + dfs(1-light, f, 1-s, ed);
			if(t < ret){
				ret = t;
			}
		}
		if(f && s){
			int t = costs[1] + dfs(1-light, 1-f, 1-s, ed);
			if(t < ret){
				ret = t;
			}
		}
	}

	return ret;
}

int solve(){
	if(N == 1){
		return costs[0];
	}
	else if(N==2){
		return max(costs[0], costs[1]);
	}
	else{
		return dfs(0,0,0,N-1);
	}
}

int main(){
	init();
	printf("%d\n", solve());
	return 0;
}