この問題は、 動的計画法(DP) を用いて解くことができます。

\(dp[\) 直近 \(3\) 席の状態 \(]=\{\) 追加で受け入れられる最大人数 \(\}\) を考えます。
ただし、直近 \(3\) 席の情報の保持の仕方を工夫します。
\(dp\) の添え字を \(3\)bit の整数であると考え、下から \(i\)bit 目を \(i\) 個前の座席の状態に対応させます。 ( \(0\) であれば空き、 \(1\) であれば人がいるとする )

DP の遷移は次のようにすればよいです。

• 初期状態は \(dp[0]=0\) 、そのほかの \(i\) について \(dp[i]=- \infty\) とする。
• \(i\) 番目の人に着目する際、 \(dp\) から \(ndp\) へと遷移させるものとする。 \(ndp[i]= - \infty\) と初期化しておく。
• \(S_i=0\) のときの遷移
  • \(dp[j]\) を \(ndp[(2 \times j) \bmod{8}]\) へと遷移させる。
  • \(dp[j]+1\) を \(ndp[(2 \times j + 1) \bmod{8}]\) へと遷移させる。ただし、遷移先が \(ndp[7]\) である場合は連続して \(3\) 人座ってしまう状態に対応するため、遷移しない。
• \(S_i=1\) のときの遷移
  • \(dp[j]\) を \(ndp[(2 \times j + 1) \bmod{8}]\) へと遷移させる。ただし、遷移先が \(ndp[7]\) である場合は連続して \(3\) 人座ってしまう状態に対応するため、遷移しない。

以上の DP を走らせることで、この問題に正解できます。

( 実は直近 \(3\) 席を保持しなくとも、直近 \(2\) 席だけ情報を保持すれば十分です。 )

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> dp(7,-1e9);
  dp[0]=0;
  for(int i=0;i<N;i++){
    vector<int> ndp(7,-1e9);
    int S;
    cin >> S;
    if(S==0){
      for(int j=0;j<7;j++){
        int x=((j<<1)&7);
        int y=x+1;
        if(x<7){ ndp[x]=max(ndp[x],dp[j]); }
        if(y<7){ ndp[y]=max(ndp[y],dp[j]+1); }
      }
    }
    else{
      for(int j=0;j<7;j++){
        int x=((j<<1)&7)+1;
        if(x<7){ ndp[x]=max(ndp[x],dp[j]); }
      }
    }
    dp=ndp;
  }
  cout << (*max_element(dp.begin(),dp.end())) << "\n";
  return 0;
}