BZOJ 3427 Bytecomputer

Link

Solution

直观的感受就是最后答案一定是\(-1,-1,-1,...,0,0,0,...,1,1,1\) 因为如果答案中存在了\(\{-1,0,1\}\)之外的数字,那么那一串数字一定可以少加一个\(1\)或者少减一个\(1\)。这样之后一定不会破坏非降性质,而且可以减小答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include "lucida"
using std::min;
int min(const int &x,const int &y,const int &z) {
return min(x,min(y,z));
}
const int MAXN=1000000+11,INF=0x1f1f1f1f;
int main() {
static int a[MAXN],f[3][MAXN];
#define f(x) f[(x)+1]
memset(f,31,sizeof(f));
freopen("input","r",stdin);
int n;is>>n;
is>>a[1];
f(a[1])[1]=0;
for(int i=2;i<=n;++i) {
is>>a[i];
f(-1)[i]=f(-1)[i-1]+a[i]+1;
if(a[i]!=-1)
f(0)[i]=f(-1)[i-1]+a[i];
if(a[i]==0)
chkmn(f(0)[i],min(f(-1)[i-1],f(0)[i-1]));
f(1)[i]=f(1)[i-1]+1-a[i];
if(a[i]==1)
chkmn(f(1)[i],min(f(-1)[i-1],f(0)[i-1],f(1)[i-1]));
}
int Ans=min(f(-1)[n],f(0)[n],f(1)[n]);
if(Ans==INF)
os<<"BRAK"<<'\n';
else
os<<Ans<<'\n';
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利