メモ

自分に向けて書いたメモを取り扱っています.

JOI 2012-2013 本選 問題1 電飾

反転回数は最大でも1回かと思っていたけど2回だった。反省

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 前回反転させた, 前回のランプ, 場所
int dp[3][2][100001];

int main() {
	int n, k, ans = 0;
	vector<bool> a;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> k;
		a.push_back(k);
	}

	dp[0][a[0]][0] = dp[1][!a[0]][0] = 1;

	for(int i = 1; i < n; i++) {
		dp[0][a[i]][i] = max(dp[0][a[i]][i], dp[0][!a[i]][i-1] + 1);
		dp[1][!a[i]][i] = max(dp[1][!a[i]][i], dp[1][a[i]][i-1] + 1);
		dp[1][!a[i]][i] = max(dp[1][!a[i]][i], dp[0][a[i]][i-1] + 1);
		dp[2][a[i]][i] = max(dp[2][a[i]][i], dp[2][!a[i]][i-1] + 1);
		dp[2][a[i]][i] = max(dp[2][a[i]][i], dp[1][!a[i]][i-1] + 1);
		ans = max(ans, dp[0][a[i]][i]);
		ans = max(ans, dp[1][!a[i]][i]);
		ans = max(ans, dp[2][a[i]][i]);
	}

	cout << ans << endl;
}