[POI2013]BAJ-Bytecomputer

https://zybuluo.com/ysner/note/1238171

题面

给一个只包含{-1,0,1})的数列，每次操作可以让a[i]+=a[i-1])，求最少操作次数使得序列单调不降。

nleq10^6)

解析

显然只能设状态f[i][j])表示已处理完第1-i)个数，第i)个数转化为j-1)的最小操作次数。
本题难度在于考虑转移条件。
话说我一开始是这么写的：（充分体现了我蒟蒻的本质)

  fpi,0,n) dp[i][0]=dp[i][1]=dp[i][2]=inf;
  dp[1][a[1]+1]=1;
  fpi,2,n)
    {
      ifa[i]==-1)
    {
      dp[i][0]=dp[i-1][0];
          //dp[i][1]=dp[i-1][2];
      dp[i][2]=dp[i-1][2]+2;
    }
      ifa[i]==0)
    {
      dp[i][0]=dp[i-1][0]+1;
      dp[i][1]=dp[i-1][1];
      dp[i][2]=dp[i-1][2]+1;
    }
      ifa[i]==1)
    {
      dp[i][0]=dp[i-1][0]+2;
      dp[i][1]=dp[i-1][0]+1;
      dp[i][2]=dp[i-1][2];
    }
    }
  re ll ans=mindp[n][0],mindp[n][1],dp[n][2]));

然后答案大了很多。

那应该怎样转移呢？

条件1)：转化完后，前后二数应不降。
条件2)：如果当前数不变，可接受前一数满足条件1)的所有方案的最小值。
条件3)：如果当前数变小，若前一数为-1)，可接受符合条件1)的所有方案；否则，只能接受j=0)的方案。
条件4)：如果当前数变大，若前一数为1)，可接受符合条件1)的所有方案；否则，只能接受j=2)的方案。

至于一些细节如取min)、对答案的贡献等自己想想吧。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define inf 1e18
#define maxa,b) a)>b)?a):b))
#define mina,b) a)<b)?a):b))
#define fpi,a,b) forre int i=a;i<=b;i++)
#define fqi,a,b) forre int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=1e6+100;
ll dp[N][3],n,a[N];
il ll gi)
{
   re ll x=0,t=1;
   re char ch=getchar);
   whilech!='-'&&ch<'0'||ch>'9')) ch=getchar);
   ifch=='-') t=-1,ch=getchar);
   whilech>='0'&&ch<='9') x=x*10+ch-48,ch=getchar);
   return x*t;
}
int main)
{
  n=gi);fpi,1,n) a[i]=gi);
  fpi,0,n) dp[i][0]=dp[i][1]=dp[i][2]=inf;
  dp[1][a[1]+1]=0;
  fpi,2,n)
    {
      ifa[i]==-1)
    {
      dp[i][0]=dp[i-1][0];
      dp[i][1]=a[i-1]==1)?mindp[i-1][0],dp[i-1][1])+1:inf;
      dp[i][2]=a[i-1]==1)?mindp[i-1][0],mindp[i-1][1],dp[i-1][2]))+2:dp[i-1][2]+2;
    }
      ifa[i]==0)
    {
      dp[i][0]=dp[i-1][0]+1;
      dp[i][1]=mindp[i-1][1],dp[i-1][0]);
      dp[i][2]=a[i-1]==1)?mindp[i-1][0],mindp[i-1][1],dp[i-1][2]))+1:dp[i-1][2]+1;
    }
      ifa[i]==1)
    {
      dp[i][0]=dp[i-1][0]+2;
      dp[i][1]=a[i-1]==-1)?mindp[i-1][0],dp[i-1][1])+1:dp[i-1][0]+1;
      dp[i][2]=mindp[i-1][0],mindp[i-1][1],dp[i-1][2]));
    }
    }
  re ll ans=mindp[n][0],mindp[n][1],dp[n][2]));
  ifans>=inf) puts"BRAK");
  else printf"%lld
",ans);
  return 0;
}