Codeforces 201 C. Fragile Bridges

問題

n個の足場がn-1個の橋で一直線上につながっている。
i番目の橋は、a[i]回渡ると壊れる。

今、好きな足場から出発して、壊れていない橋を渡るということを繰り替えす。
橋を渡る回数の最大値は何回か、求めよ。

制約条件

n≦10^5
a[i]≦10^9

方針

渡り方を折れ線で考えると、ループまたは一本の線分になっている。
このような渡り方のうち、最適なものを動的計画法により求める。

動的計画法による。
左からと右からの2回DPする。

まずは左から、
dp[i][0]を、i番目以下の橋のみを使い、最後にiに居て、頂点iからi-1に偶数回渡っているときの、渡る回数の最大値、
dp[i][1]を、i番目以下の橋のみを使い、最後にiに居て、頂点iからi-1に奇数回渡っているときの、渡る回数の最大値とする。

これを更新していくことで、それぞれの最適解がO(n)で求まる。

同様の最大値を右からも求める。
あとは、それぞれの頂点について、左側の最適値と右側の最適値を足したものが、全体の最適解になる。

ソースコード

int n, a[100010];
ll dp[100010][2], dp2[100010][2];

void solve(ll dp[100010][2]){
	rep(i, n - 1){
		if(a[i] > 1)
		dp[i + 1][0] = dp[i][0] + a[i] / 2 * 2;
		if(a[i] > 0)
		dp[i + 1][1] = max(dp[i][0], dp[i][1]) + (a[i] % 2 ? a[i]: a[i] - 1);
	}
}

void run()
{
	cin >> n;
	rep(i, n - 1) cin >> a[i];
	
	solve(dp);
	reverse(a, a + n - 1);
	solve(dp2);
	
	ll ans = 0;
	rep(i, n){
		rep(j, 2) rep(k, 2)
		ans = max(ans, dp[i][j] + dp2[n - i - 1][k]);
		
	}
	cout << ans << endl;
}