1 /************************************************************** 2     Problem: 3427 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:808 ms 7     Memory:16432 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13  14 using namespace std;15 const int N = 1000005;16 const int inf = 1e9;17  18 int a[N], f[N][3];19 int n, ans = inf;20  21 inline int read() {22     int x = 0, sgn = 1;23     char ch = getchar();24     while (ch < ‘0‘ || ‘9‘ < ch) {25         if (ch == ‘-‘) sgn = -1;26         ch = getchar();27     }28     while (‘0‘ <= ch && ch <= ‘9‘) {29         x = x * 10 + ch - ‘0‘;30         ch = getchar();31     }32     return sgn * x;33 }34  35 int main() {36     int i, j, k;37     int t, to;38     n = read();39     for (i = 1; i <= n; ++i)40         a[i] = read();41     memset(f, 127, sizeof(f));42     f[1][a[1] + 1] = 0;43     for (i = 1; i < n; ++i)44         for (j = 0; j <= 2; ++j) if (f[i][j] < inf)45             for (t = j - 1, k = 0; k <= 2; ++k) {46                 to = a[i + 1] + k * t;47                 if (to >= -1 && to <= 1 && to >= t)48                     f[i + 1][to + 1] = min(f[i + 1][to + 1], f[i][j] + k);49             }50     for (i = 0; i <= 2; ++i)51         ans = min(ans, f[n][i]);52     if (ans == inf) puts("BRAK");53     else printf("%d\n", ans);54     return 0;55 }