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