bzoj3427: Poi2013 Bytecomputer
可以发现，最后剩下的数一定由-1,0,1,组成。
证明：如果有一个位置上的数>1，则这个数一定在之前能变成1，如果下一位是-1,需要至少两次才能满足条件，而0,1,需要1次，这和当前位是1的效果是1一样的，所以猜想得证。
然后就dp求就可以了，转移很简单。
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define ll long long using namespace std; int read() { char ch=getchar();int f=0,x=1; while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();} while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();} return f*x; } int f[1000005][3],n,a[1000005]; int main() { memset(f,0x7f7f7f7f,sizeof(f)); n=read(); for(int i=1;i<=n;i++) a[i]=read(); f[1][a[1]+1]=0; for(int i=2;i<=n;i++) { if(a[i]==1) { f[i][0]=min(f[i][0],f[i-1][0]+2); f[i][1]=min(f[i][1],f[i-1][0]+1); f[i][2]=min(f[i-1][0],f[i-1][1]); f[i][2]=min(f[i][2],f[i-1][2]); } else if(a[i]==-1) { f[i][0]=f[i-1][0]; f[i][2]=min(f[i][2],f[i-1][2]+2); } else { f[i][1]=min(f[i-1][1],f[i-1][0]); f[i][0]=min(f[i][0],f[i-1][0]+1); f[i][2]=min(f[i][2],f[i-1][2]+1); } //cout<<f[i][0]<<" "<<f[i][1]<<" "<<f[i][2]<<endl; } if(f[n][0]>n*2&&f[n][1]>2*n&&f[n][2]>2*n) puts("BRAK"); else cout<<min(f[n][0],min(f[n][1],f[n][2])); } |
Orz