ZOJ Monthly, July 2012 - G : Treasure Hunt III
問題概要
n(<10^5)個の部屋が環状に並んでいる。最初は部屋Sにいる。これから最大T回部屋を移動して各部屋にある価値v[i]の宝を集めたい。ただし、ある部屋の宝をとるとその両隣の部屋の宝が消える。
解法
最適ルートは、右→左か左→右なので、今いる位置から右に進んだ場合と左に進んだ場合でそれぞれDPして最適解を求めておき、最後にその2つをマージするようにすればよい。うまく実装する自信がなかったので、初期位置をとる場合ととらない場合で場合分けした。場合分けも2種類くらいならまあ。
acceptされたコード
#include <cstdio> #include <algorithm> using namespace std; typedef long long int64; const int64 INF = 1LL<<60; const int MAX_N = 50000; int N, S, T; int64 as[MAX_N + 10]; int64 opt[2][MAX_N + 1][2]; //( (right or left), i-th, used? ) inline int getNxt(int current, int dir) { current += (dir ? 1 : -1); if (current == N) { current = 0; } if (current < 0) { current = N - 1; } return current; } int64 solve() { int64 ans = 0; if (N == 1) { return as[0]; } as[N] = as[0]; as[N+1] = as[1]; //Sを使う場合 for (int dir = 0; dir < 2; ++dir) { int cur = S, nxt = getNxt(cur, dir); opt[dir][0][1] = as[S]; opt[dir][0][0] = -INF; for (int i = 0; i < N - 1; ++i) { opt[dir][i+1][1] = (i == N - 2 ? 0 : opt[dir][i][0] + as[nxt]); opt[dir][i+1][0] = max(opt[dir][i][1], opt[dir][i][0]); cur = nxt; nxt = getNxt(cur, dir); } } if (T >= N - 1) { ans = max(ans, opt[0][N-1][1]); ans = max(ans, opt[0][N-1][0]); } else { //r : 右に何歩歩いたか for (int r = 0; r <= T; ++r) { int64 tmp = max(opt[0][r][0], opt[0][r][1]); int res = T - 2*r; if (res >= 0) { tmp += max(opt[1][res][0], opt[1][res][1]); tmp -= as[S]; } ans = max(ans, tmp); } //l : 左に何歩歩いたか for (int l = 0; l <= T; ++l) { int64 tmp = max(opt[1][l][0], opt[1][l][1]); int res = T - 2*l; if (res >= 0) { tmp += max(opt[0][res][0], opt[0][res][1]); tmp -= as[S]; } ans = max(ans, tmp); } } //Sを使わない場合 for (int dir = 0; dir < 2; ++dir) { int cur = S, nxt = getNxt(cur, dir); opt[dir][0][0] = 0; opt[dir][0][1] = -INF; for (int i = 0; i < N - 1; ++i) { opt[dir][i+1][1] = opt[dir][i][0] + as[nxt]; opt[dir][i+1][0] = max(opt[dir][i][1], opt[dir][i][0]); cur = nxt; nxt = getNxt(cur, dir); } } if (T >= N - 1) { ans = max(ans, opt[0][N-1][1]); ans = max(ans, opt[0][N-1][0]); } else { for (int r = 0; r <= T; ++r) { int64 tmp = max(opt[0][r][0], opt[0][r][1]); int res = T - 2*r; if (res >= 0) { tmp += max(opt[1][res][0], opt[1][res][1]); } ans = max(ans, tmp); } //l : 左に何歩歩いたか for (int l = 0; l <= T; ++l) { int64 tmp = max(opt[1][l][0], opt[1][l][1]); int res = T - 2*l; if (res >= 0) { tmp += max(opt[0][res][0], opt[0][res][1]); } ans = max(ans, tmp); } } return ans; } bool init() { if (scanf("%d%d%d", &N, &T, &S) == EOF) { return false; } --S; for (int i = 0; i < N; ++i) { scanf("%lld", as + i); } return N > 0; } int main() { for (;init();) { printf("%lld\n", solve()); } return 0; }