题目描述
A sequence of N integers I1,I2…In from the set {-1,0,1} is given. The bytecomputer is a device that allows the following operation on the sequence: incrementing I(i+1) by I(i) for any 1<=I<=N. There is no limit on the range of integers the bytecomputer can store, i.e., each I(i) can (in principle) have arbitrarily small or large value.
Program the bytecomputer so that it transforms the input sequence into a non-decreasing sequence (i.e., such that I1<=I2<=…I(n)) with the minimum number of operations.
给定一个{-1,0,1}组成的序列,你可以进行x[i]=x[i]+x[i-1]这样的操作,求最少操作次数使其变成不降序列。
题解
显然这个序列最后是一个 -1 -1 -1 0 0 0 1 1 1的样子 也就是说每个地方都只会有3种取值，所以记
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示
i
i
i这个位置值为
j
j
j需要的操作次数。 PS：这种DP有一个鲜明的提示，值由值更新而来，值域小。所以一维用来转移 转移的时候注意我们不仅可以直接用上一个位置被更新后的值来更新，也可以事先用原来的值更新。
代码
#include <bits/stdc++.h>
#define maxn 1000005
#define INF 0x3f3f3f3f
using namespace std;
int f[maxn][3],a[maxn],n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[1][0]=f[1][1]=f[1][2]=INF;
f[1][a[1]+1]=0;
for(int i=2;i<=n;i++){
if(a[i]==-1){
f[i][0]=f[i-1][0];
f[i][1]=(a[i-1]==1)?min(f[i-1][0],f[i-1][1])+1:INF;
f[i][2]=(a[i-1]==1)?min(f[i-1][0],min(f[i-1][1],f[i-1][2]))+2:f[i-1][2]+2;
}
if(a[i]==0){
f[i][0]=f[i-1][0]+1;
f[i][1]=min(f[i-1][0],f[i-1][1]);
f[i][2]=(a[i-1]==1)?min(f[i-1][0],min(f[i-1][1],f[i-1][2]))+1:f[i-1][2]+1;
}
if(a[i]==1){
f[i][0]=f[i-1][0]+2;
f[i][1]=(a[i-1]==-1)?min(f[i-1][0],f[i-1][1])+1:f[i-1][0]+1;
f[i][2]=min(f[i-1][0],min(f[i-1][1],f[i-1][2]));
}
}
int ans=min(f[n][0],min(f[n][1],f[n][2]));
if(ans>=INF) puts("BRAK");
else cout<<ans<<endl;
}
