Codeforces Round #127 (Div. 1) C : Fragile Bridges

問題概要

N(<10^5)個の島が一列にならんでいる。隣り合う島を橋が結んでいる。橋はa[i]回通ると崩壊する。いずれかの島からスタートしてできるだけたくさん橋を渡りたい。最大何回渡れるか求める問題。

解法

ある島を基準にして、右(or 左)に行って何回橋を渡れるか、を戻ってこれる場合と戻ってくる必要がない場合に分けてそれぞれdpで計算すればよい。

acceptされたコード

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_N = (int)(1e5);

int N;
int as[MAX_N - 1];
int64 opt[2][MAX_N];
int64 canBack[2][MAX_N];

void init() {
	cin >> N;
	for (int i = 0; i < N-1; ++i) {
		cin >> as[i];
	}
}

int64 solve() {
	canBack[0][0] = 0;
	for (int i = 0; i < N - 1; ++i) {
		if (as[i] == 1) {
			canBack[0][i + 1] = 0;
		}
		else {
			canBack[0][i + 1] = canBack[0][i] + (as[i] & (~1));
		}
	}
	canBack[1][N - 1] = 0;
	for (int i = N - 1 ; i > 0; --i) {
		if (as[i - 1] == 1) {
			canBack[1][i - 1] = 0;
		}
		else {
			canBack[1][i - 1] = canBack[1][i] + (as[i - 1] & (~1));
		}
	}

	opt[0][0] = 0;
	for (int i = 0; i < N - 1; ++i) {
		opt[0][i + 1] = 1 + max(opt[0][i], canBack[0][i]) + ((as[i] - 1) & (~1));
	}
	opt[1][N - 1] = 0;
	for (int i = N - 1 ; i > 0; --i) {
		opt[1][i - 1] = 1 + max(opt[1][i], canBack[1][i]) + ((as[i - 1] - 1) & (~1));
	}

	int64 ans = 0;
	for (int i = 0; i < N; ++i) {
		ans = max( ans, opt[0][i] + canBack[1][i]);
		ans = max( ans, opt[1][i] + canBack[0][i]);
		ans = max( ans, canBack[0][i] + canBack[1][i]);
	}

	return ans;
}

int main() {
	init();
	cout << solve() << endl;

	return 0;
}