BZOJ1482 : [Balkan2017]Cats

若猫和狗中至少有一个出现了$0$次，那么答案显然是$0$，否则若狮子出现了$0$次，那么显然无解。

那么现在至少有一个动物保持原地不同，其它动物恰好移动一次。

如果全部猫都不动而全部狗都动，那么可以贪心求出答案，最多移动一个狮子。

同理可以处理全部猫动而全部狗都不动的情况。

现在考虑同时存在猫和狗不动的情况，那么动的猫和狗一定是移动到不动的同类旁边，而狮子起到间隔作用。

设$f[i][j][k][S]$表示考虑前$i$个动物，目前手上剩余可以调控的狮子数为$j$(可以为负，表示后面的狮子往前动)，下一个动物可以是$k$，不动的动物种类为$S$的最小移动次数，直接转移即可。

时间复杂度$O(n^2)$。

#include<cstdio>

const int N=5010,inf=1000000;

int Case,n,m,o,i,j,k,S,w,a[N],b[N],cnt[3],f[2][N*2][2][4],ans;

inline void up(int&a,int b){a>b?(a=b):0;}

int cal(int x){

  int i,t=0;

  for(i=1;i<=n;i++)if(a[i]!=(x^1))b[++t]=a[i];

  for(i=1;i<t;i++)if(b[i]==2&&b[i+1]==2)return n-t;

  if(b[1]==2||b[t]==2)return n-t;

  return n-t+1;

}

int solve(){

  scanf("%d",&n);

  for(i=0;i<3;i++)cnt[i]=0;

  for(i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;

  if(!cnt[0]||!cnt[1])return 0;

  if(!cnt[2])return -1;

  m=cnt[2];

  up(m,n/2+5);

  for(o=0,j=-m;j<=m;j++)for(k=0;k<2;k++)for(S=0;S<4;S++)f[0][j+N][k][S]=inf;

  f[0][N][0][0]=f[0][N][1][0]=0;

  for(i=0;i<n;i++,o^=1){

    for(j=-m;j<=m;j++)for(k=0;k<2;k++)for(S=0;S<4;S++)f[o^1][j+N][k][S]=inf;

    if(a[i+1]==0)for(j=-m;j<=m;j++)for(k=0;k<2;k++)for(S=0;S<4;S++)if(f[o][j+N][k][S]<inf){

      w=f[o][j+N][k][S];

      up(f[o^1][j+N][k][S],w+1);

      up(f[o^1][j+N-(k==1)][0][S|1],w);

    }

    if(a[i+1]==1)for(j=-m;j<=m;j++)for(k=0;k<2;k++)for(S=0;S<4;S++)if(f[o][j+N][k][S]<inf){

      w=f[o][j+N][k][S];

      up(f[o^1][j+N][k][S],w+1);

      up(f[o^1][j+N-(k==0)][1][S|2],w);

    }

    if(a[i+1]==2)for(j=-m;j<=m;j++)for(k=0;k<2;k++)for(S=0;S<4;S++)if(f[o][j+N][k][S]<inf){

      w=f[o][j+N][k][S];

      up(f[o^1][j+N+1][k][S],w+1);

      up(f[o^1][j+N][0][S],w);

      up(f[o^1][j+N][1][S],w);

    }

  }

  ans=cal(0);

  up(ans,cal(1));

  for(k=0;k<2;k++)up(ans,f[o][N][k][3]);

  return ans;

}

int main(){

  scanf("%d",&Case);

  while(Case--)printf("%d\n",solve());

  return 0;

}