AOJ 0534 連鎖
以前、どうしてもバグが取れなくてあきらめていた問題
実装難しすぎ
解法
強実装。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10000; int N; int main(){ while(scanf("%d", &N), N!=0){ int a[N]; for(int i = 0; i < N; i++) scanf("%d", &a[i]); int ans = N; for(int i = 0; i < N; i++){ int p = i, q = i+1; int t = 0; for(int j = 1; j <= 3; j++){ if(a[i] == j) continue; int tt = a[i]; a[i] = j; bool update = true; while(update){ update = false; int c = a[p]; int n = 0; int pp = p, qq = q; for(; p >= 0 && a[p] == c; p--) n++; for(; q < N && a[q] == c; q++) n++; if(n >= 4){ t += n; update = true; }else{ p = pp; q = qq; } c = a[q]; n = 0; pp = p; qq = q; for(; p >= 0 && a[p] == c; p--) n++; for(; q < N && a[q] == c; q++) n++; if(n >= 4){ t += n; update = true; }else{ p = pp; q = qq; } } a[i] = tt; ans = min(ans, N - t); } } printf("%d\n", ans); } return 0; }