fork download
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=1000000+10;
  27.  
  28. int n;
  29. int x[MAX];
  30. //if x_i<0 then x_i+x_{i-1}<x_{i-1}
  31. //最终结果一定是-1 -1 -1 -1...0 0 0 0...1 1 1 1的形式
  32. int f[MAX][3];
  33.  
  34. void update(int& a,int b)
  35. {
  36. if(b!=-1 && (a==-1 || b<a))
  37. a=b;
  38. }
  39.  
  40. int main()
  41. {
  42. #ifndef ONLINE_JUDGE
  43. // freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  44. #endif
  45. int i,j,k;
  46. scanf("%d",&n);
  47. REP(i,1,n)
  48. scanf("%d",&x[i]);
  49. memset(f,-1,sizeof f);
  50. f[1][x[1]+1]=0;
  51. for(i=2;i<=n;++i)
  52. REP(j,-1,1)
  53. if(f[i-1][j+1]!=-1)
  54. REP(k,0,3)
  55. if(j*k+x[i]<=1 && j*k+x[i]>=j)
  56. update(f[i][j*k+x[i]+1],f[i-1][j+1]+k);
  57. int ans=-1;
  58. REP(j,-1,1)
  59. update(ans,f[n][j+1]);
  60. if(ans==-1)
  61. printf("BRAK\n");
  62. else printf("%d\n",ans);
  63. return 0;
  64. }
  65.  
Success #stdin #stdout 0s 18968KB
stdin
6
-1 1 0 -1 0 1
stdout
3