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; }