BZOJ 3427 Bytecomputer

发表于 | 更新于

Link

Solution

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

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;
}