[POI 2013]Bytecomputer(DP)

题目链接

题目大意

给你一个长度为，问至少要做多少次操作，才能让整个序列变成非降序列

思路

可以发现，最终的序列是一定是-1 -1 -1…-1 -1 -1 0 0 0…0 0 0 1 1 1…1 1 1的形式，肯定没有2或者更大的数字，因为出现这样大的数字是毫无必要的，会增加操作次数。那么可以通过DP解决此题，用个元素被执行了多少次操作即可。

代码;int f[MAXN][3],a[MAXN],n;int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);memset(f,INF,sizeof(f));f[1][a[1]+1]=0;for(int i=1;i<n;i++)for(int j=0;j<=2;j++)for(int k=0;k<=2;k++){if(f[i][j]==INF) continue;int newj=a[i+1]+(j-1)*k;if(newj>=-1&&newj<=1&&newj>=(j-1))f[i+1][newj+1]=min(f[i+1][newj+1],f[i][j]+k);}int ans=INF;for(int i=0;i<=2;i++)ans=min(ans,f[n][i]);if(ans==INF) printf(“BRAK\n”);else printf(“%d\n”,ans);return 0;}

，有理想在的地方，地狱就是天堂