2012-2013 JOI予選 問6 : Gifts
問題文 : お土産購入計画
解法 :
上または左に3回しか戻れないということは, 7ターン以上前の状態に戻ることが不可能ということを指す.
そこで, 6ターン前までに移動した方向を, bitで管理して持つ(e.x: 00->右 01->下, 10->左, 11->上).
1つの方向を2bitで管理できるので, 6 * 2 = 12bitあればbitでの移動方向の管理が可能である.
この情報を元に, 純粋に再帰を行い, その過程をメモすれば良い.
メモする内容は, 「6ターン前までの移動方向」「今いる座標」「あと何回上か左に動けるか」があれば十分である.
コード :
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int w, h, k; int memo[1 << 12][4][50][50]; int mask; int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}; char field[64][64]; bool check(int ny, int nx) { return (0 <= ny && ny < h && 0 <= nx && nx < w); } int getMax(int bit, int left, int ty, int tx) { if (memo[bit][left][ty][tx] != -1) return (memo[bit][left][ty][tx]); if (ty == h - 1 && tx == w - 1 && left == 0){ return (0); } int px = tx, py = ty; bool same = false; for (int i = 0; i < 2 * k; i++){ px += -dx[(bit >> (2 * i)) & 3]; py += -dy[(bit >> (2 * i)) & 3]; if (px == tx && py == ty){ same = true; break; } } int ret = 0; if (!same && field[ty][tx] != '.') ret += field[ty][tx] - '0'; int val = -999999; for (int i = 0; i < 4; i++){ if (left == 0 && i >= 2) break; int nx = tx + dx[i], ny = ty + dy[i]; if (check(ny, nx) && field[ny][nx] != '#'){ val = max(val, getMax(((bit << 2) | i) & mask, left - (i >= 2), ny, nx) + ret); } } return (memo[bit][left][ty][tx] = val); } int main() { scanf("%d %d %d", &h, &w, &k); mask = (1 << (4 * k)) - 1; for (int i = 0; i < h; i++){ scanf("%s", field[i]); } memset(memo, -1, sizeof(memo)); int res = getMax(0, k, 0, 0); printf("%d\n", res < 0 ? 0 : res); return (0); }
21 704 19 253 274