Submission #66853497

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int T, tc;
int N;
char S[212345];
int memo[212345][3];
int memo_tc[212345][3];
int calc(int pos, int status) {
  int ans, candidate;
  if (pos >= N) return 0;
  if (memo_tc[pos][status] == tc) return memo[pos][status];
  /* 変えない */
  ans = calc(pos + 1, status) + (S[pos] != "010"[status]);
  /* 次に進める */
  if (status < 2) {
    candidate = calc(pos + 1, status + 1) + (S[pos] != "10"[status]);
    if (candidate < ans) ans = candidate;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int T, tc;

int N;
char S[212345];

int memo[212345][3];
int memo_tc[212345][3];

int calc(int pos, int status) {
	int ans, candidate;
	if (pos >= N) return 0;
	if (memo_tc[pos][status] == tc) return memo[pos][status];
	/* 変えない */
	ans = calc(pos + 1, status) + (S[pos] != "010"[status]);
	/* 次に進める */
	if (status < 2) {
		candidate = calc(pos + 1, status + 1) + (S[pos] != "10"[status]);
		if (candidate < ans) ans = candidate;
	}
	memo[pos][status] = ans;
	memo_tc[pos][status] = tc;
	return ans;
}

int main(void) {
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 1; tc <= T; tc++) {
#if 0
		int i;
		int cnt = 0, combo = 0, max_combo = 0;
		int first = -1, last = -1;
		int cnt2 = 0, candidate;
#endif
		if (scanf("%d", &N) != 1) return 1;
		if (scanf("%212344s", S) != 1) return 1;
#if 0
		for (i = 0; i < N; i++) {
			if (S[i] == '1') {
				cnt++;
				combo++;
				if (combo > max_combo) max_combo = combo;
				if (first == -1) first = i;
				last = i;
			} else {
				combo = 0;
			}
		}
		candidate = cnt - max_combo;
		for (i = first; i <= last; i++) {
			if (S[i] != '1') cnt2++;
		}
		printf("%d\n", candidate <= cnt2 ? candidate : cnt2);
#endif
		printf("%d\n", calc(0, 0));
	}
	return 0;
}

/*

連続する同じ数字を1つにして 010101… みたいな形にしたとき、「1」を1個以下にできれば勝ち
1回の操作で、「1」を1個減らせる

↑大嘘 1回の操作で変えられるのは範囲ではなく、1要素のみ

とりうる戦略は
・最大の「1」のかたまりだけを残し、他の「1」を全て潰す
・「1」の間に挟まる「0」を全て潰す

↑嘘 ハイブリッドの可能性もある

1
13
1000001110111

「0：0にする」「1：1にする」「2：0にする」の状態を持つ
それぞれの数字について、状態を「変えない」「次に進める」を選択するメモ化探索

*/

Submission Info

Judge Result