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