AOJ 0245 Time Sale
解法
動的計画法で解きました。
dp[x][y][state] = state の状態で(x, y) への最短コスト
state はビットで管理して、商品に隣接するセルをIterator で回して幅優先探索をかけ、min をもって更新していきます。
state にたどりつけたらans に得ることのできた割引額を入れておき、後でmax をとって答えとします。
設計メモ
dp ... INF(行けない)でクリア ans ... -1(行けない)でクリア start : 初期位置 dp[ start.x ][ start.y ][ 0 ] <- bfs で埋める ans[ 0 ] = 0 for( from : 0 ~ 1<<N ) for( to : 0 ~ N ) if ((from>>to)0x01) == 0x00 then ... 行ったところへは行かない req <- 商品, toに隣接するセル(x, y) dp[x][y][ from | (1<<to) ] = min( dp[x][y][ from | (1<<to) ], dp[x][y][from] ) x, y をstart として[from | (1<<to)] のdp表をmin で更新する ans[from | (1<<to)] = ans[from] + d[to]
あとは割引の始まりと終わりに注意して書いていきます。
早く着いてしまったら、うろちょろして時間をかけます。
ソースコード
import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main{ Scanner sc; int INF = 1<<27; int[][] map; int X, Y; int N; int[] start; int[] d_list; int[] s_list; int[] e_list; int[][] ofs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; int[][][] dp; int[] ans; void solve(){ dp = new int[X][Y][1<<N]; ans = new int[1<<N]; for(int x=0; x<X; ++x)for(int y=0; y<Y; ++y)for(int n=0; n<1<<N; ++n){ dp[x][y][n] = INF; } Arrays.fill(ans, -1); dp[start[0]][start[1]][0] = 0; ans[0] = 0; bfs(0, start[0], start[1], 0); for( int from = 0; from < 1<<N; ++from ){ for( int to = 0; to < N; ++to ){ if( ((from>>to)&0x01) == 0x00 ){ LinkedList<ArrayList<Integer>> req = get_req( to ); Iterator<ArrayList<Integer>> ite = req.iterator(); while(ite.hasNext()){ ArrayList<Integer> e = ite.next(); int x = e.get(0); int y = e.get(1); if( dp[x][y][from] < e_list[to] ){ if( s_list[to] <= dp[x][y][from] ){ dp[x][y][from | (1<<to)] = Math.min(dp[x][y][from | (1<<to)], dp[x][y][from]); bfs(from | (1<<to), x, y, dp[x][y][from | (1<<to)]); ans[from | (1<<to)] = ans[from] + d_list[to]; }else{ assert( dp[x][y][from] < s_list[to] ); int d = s_list[to] - dp[x][y][from]; if( d%2==1 ) ++d; assert( s_list[to] <= dp[x][y][from] + d ); if( dp[x][y][from] + d < e_list[to] ){ dp[x][y][from | (1<<to)] = Math.min(dp[x][y][from | (1<<to)], dp[x][y][from] + d); bfs(from | (1<<to), x, y, dp[x][y][from | (1<<to)]); ans[from | (1<<to)] = ans[from] + d_list[to]; } } } } } } } int max = -1; for(int i=0; i<1<<N; ++i){ max = Math.max(max, ans[i]); } assert(max>=0); System.out.println(max); } void bfs(int n, int sx, int sy, int scost){ Queue<Integer> qx = new LinkedList<Integer>(); Queue<Integer> qy = new LinkedList<Integer>(); qx.add(sx); qy.add(sy); boolean[][] done = new boolean[Y][X]; done[sy][sx] = true; while(qx.size()>0){ int[] p = new int[]{qx.poll(), qy.poll()}; assert(qx.size() == qx.size()); for( int[] ope : ofs ){ int[] e = new int[]{p[0], p[1]}; e[0] += ope[0]; e[1] += ope[1]; if( isSafe(e[0], e[1]) ){ if( !done[e[1]][e[0]] && map[e[1]][e[0]] == -1 ){ done[e[1]][e[0]] = true; dp[e[0]][e[1]][n] = Math.min(dp[e[0]][e[1]][n], dp[p[0]][p[1]][n] + 1); qx.add(e[0]); qy.add(e[1]); } } } } } void run(){ sc = new Scanner(System.in); while(true){ X = ni(); Y = ni(); if((X|Y)==0) break; map = new int[Y][X]; start = new int[2]; for(int y=0; y<Y; ++y)for(int x=0; x<X; ++x){ char c = sc.next().charAt(0); if(c=='.'){ map[y][x] = -1; }else if(c=='P'){ map[y][x] = -1; start[0] = x; start[1] = y; }else{ map[y][x] = c - '0'; } } N = ni(); d_list = new int[N]; s_list = new int[N]; e_list = new int[N]; for(int i=0; i<N; ++i){ int g = ni(); int d = ni(); int s = ni(); int e = ni(); assert(g==i); d_list[i] = d; s_list[i] = s; e_list[i] = e; } solve(); } sc.close(); } LinkedList<ArrayList<Integer>> get_req(int trg){ HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>(); for(int y=0; y<Y; ++y)for(int x=0; x<X; ++x){ int[] e = new int[]{x, y}; if(map[e[1]][e[0]] == -1){ for(int[] ope : ofs){ int[] buf = new int[]{e[0], e[1]}; buf[0] += ope[0]; buf[1] += ope[1]; if(isSafe(buf[0], buf[1])){ if( map[buf[1]][buf[0]] == trg ){ ArrayList<Integer> p = new ArrayList<Integer>(); p.add(e[0]); p.add(e[1]); set.add(p); } } } } } LinkedList<ArrayList<Integer>> list = new LinkedList<ArrayList<Integer>>(); Iterator<ArrayList<Integer>> ite = set.iterator(); while(ite.hasNext()){ list.add(ite.next()); } return list; } int ni(){ return sc.nextInt(); } boolean isSafe(int x, int y){ return (0<=x && x<X) && (0<=y && y<Y); } public static void main(String[] args){ new Main().run(); } }
終えて
取りに行く商品に隣接するセルのリストを返すget_req 関数がごちゃごちゃしていて、制限時間ある中で勇気持って書けるか不安なコードになってしまいました。
(JDK7でもって型推論使いたい...)