CodeForces 1286A Garland (R1700)

問題

長さ $N$ の数列 $p$ が与えられます。これは長さ $N$ の順列の一部が欠けたもので、欠けたところは $p_i=0$ になっています。 $p$ が順列になるように復元したときの、 $p$ の複雑さの最小値を求めてください。ここで $p$ の複雑さとは、隣接要素のペアであって、偶奇が異なるようなものの個数とします。

制約

$1 \le N \le 100$
$0 \le p_i \le N\ (1 \le i \le N)$

考察

偶奇だけが重要なので $mod\ 2$ で考えます。まず、 $p$ を $2$ で割った余りで置き換えておきます( $p_i=0$ だったところは $p_i=-1$ とします)。左から順番に復元していくことにします。すると、それまでに使った $0と1$ の個数と、最後の要素の偶奇が同じであれば、後のことを考えるとコストが小さいほうがよいので、次のようなDPが考えられます。

$$ dp[i][j][k]:=左からi個復元して、それまでで0をj個使っていて、最後の要素の偶奇がkのときのコストの最小値 $$ 使った $1$ の個数は $i-j$ なので状態として持たなくて良いです。

$dp[i][j][k]$ からの遷移は

$0$ を置く場合 $$ chmin(dp[i+1][j+1][0],dp[i][j][k]+k) $$
$1$ を置く場合
$$ chmin(dp[i+1][j][1],dp[i][j][k]+(k\ xor\ 1)) $$

です。 $0$ と $1$ が置ける個数はそれぞれ $\lfloor N/2 \rfloor$ と $\lceil N/2 \rceil$ なので、これを超えないようにしなければなりません。

#include<bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
int dp[110][110][2];

int main()
{
   int N; cin>>N;
   vector<int> p(N);
   for(int i=0;i<N;i++) cin>>p[i];

   if(N==1){ cout<<0<<endl; return 0; }

   for(int i=0;i<N;i++){
      if(p[i]==0) p[i]=-1;
      else p[i]=p[i]%2;
   }

   memset(dp,INF,sizeof(dp));
   if(p[0]==0 or p[0]==-1) dp[1][1][0]=0;
   if(p[0]==1 or p[0]==-1) dp[1][0][1]=0;

   for(int i=1;i<N;i++) for(int j=0;j<=i;j++) for(int k=0;k<2;k++) if(dp[i][j][k]<INF){
      if((p[i]==0 or p[i]==-1) and j<N/2){
         dp[i+1][j+1][0]=min(dp[i+1][j+1][0],dp[i][j][k]+(k^0));
      }
      if((p[i]==1 or p[i]==-1) and i-j<(N+1)/2){
         dp[i+1][j+0][1]=min(dp[i+1][j+0][1],dp[i][j][k]+(k^1));
      }
   }
   cout<<min(dp[N][N/2][0],dp[N][N/2][1])<<endl;
   return 0;
}