BZOJ_3427_Poi2013 Bytecomputer_DP
Description
给定一个{-1,0,1}组成的序列,你可以进行x[i]=x[i]+x[i-1]这样的操作,求最少操作次数使其变成不降序列。
Sample Input
6
-1 1 0 -1 0 1
-1 1 0 -1 0 1
Sample Output
3
分析：容易知道最后的序列中一定只有-1,0,1
f[i][j]表示当前在第i个人，把这个数变成j的最小花费。
枚举这一位和前一位都是啥，满足能转移的条件即可。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 1000050
int a[N],f[N][3],n;
int main() {
int i;
scanf("%d",&n);
memset(f,0x3f,sizeof(f));
for(i=1;i<=n;++i) scanf("%d",&a[i]);
f[1][a[1]+1]=0;
for(i=2;i<=n;++i) {
if(a[i]==-1) {
f[i][0]=f[i-1][0];
//f[i][1]=f[i-1][2]+1;
f[i][2]=f[i-1][2]+2;
}else if(a[i]==0) {
f[i][0]=f[i-1][0]+1;
f[i][1]=min(f[i-1][1],f[i-1][0]);
f[i][2]=f[i-1][2]+1;
}else {
f[i][0]=f[i-1][0]+2;
f[i][1]=f[i-1][0]+1;
f[i][2]=min(min(f[i-1][0],f[i-1][1]),f[i-1][2]);
}
}
int tmp=min(min(f[n][0],f[n][1]),f[n][2]);
if(tmp>10000000) {
puts("BRAK");
}else printf("%d\n",tmp);
}