[POI2013]BAJ-Bytecomputer

DP

题面

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

• $n\leq10^6$

解析

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

  fp(i,0,n) dp[i][0]=dp[i][1]=dp[i][2]=inf;
  dp[1][a[1]+1]=1;
  fp(i,2,n)
    {
      if(a[i]==-1)
    {
      dp[i][0]=dp[i-1][0];
          //dp[i][1]=dp[i-1][2];
      dp[i][2]=dp[i-1][2]+2;
    }
      if(a[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;
    }
      if(a[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=min(dp[n][0],min(dp[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 max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re 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();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
int main()
{
  n=gi();fp(i,1,n) a[i]=gi();
  fp(i,0,n) dp[i][0]=dp[i][1]=dp[i][2]=inf;
  dp[1][a[1]+1]=0;
  fp(i,2,n)
    {
      if(a[i]==-1)
    {
      dp[i][0]=dp[i-1][0];
      dp[i][1]=(a[i-1]==1)?min(dp[i-1][0],dp[i-1][1])+1:inf;
      dp[i][2]=(a[i-1]==1)?min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+2:dp[i-1][2]+2;
    }
      if(a[i]==0)
    {
      dp[i][0]=dp[i-1][0]+1;
      dp[i][1]=min(dp[i-1][1],dp[i-1][0]);
      dp[i][2]=(a[i-1]==1)?min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1:dp[i-1][2]+1;
    }
      if(a[i]==1)
    {
      dp[i][0]=dp[i-1][0]+2;
      dp[i][1]=(a[i-1]==-1)?min(dp[i-1][0],dp[i-1][1])+1:dp[i-1][0]+1;
      dp[i][2]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]));
    }
    }
  re ll ans=min(dp[n][0],min(dp[n][1],dp[n][2]));
  if(ans>=inf) puts("BRAK");
  else printf("%lld\n",ans);
  return 0;
}