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

以下の DP を考えます。

\(dp[k]=\{\) 高橋君がタイル \(k\) の上にいて、 \(1,2,\dots,k\) のうち足跡を付けるタイルの最小数 \(\}\)

• \(f(h,d)\) をほこりの厚さ \(h\) 、タイルの定数 \(d\) である時にそれを踏んで足跡がつくなら \(1\) 、そうでないなら \(0\) を返す関数であるとします。

  • この関数は、問題文の指示通りに \(h>0\) かつ \(d>0\) なら \(1\) 、そうでないなら \(0\) を返せばよいです。

• 初期条件は \(dp[1]=f(H_1,D_1)\) 、それ以外の \(dp[i]=\infty\) です。

• 遷移は次の通りです。

  • \(j=i-2,i-1\) について、以下を繰り返す。
  • \(dp[i]\) に \(dp[j]+f(H_i,D_i)\) を遷移させ、より小さい方の値を残す。

• 最終的な答えは \(dp[N]\) です。

この解法の時間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int f(int h,int d){
  if(h>0 && d>0){return 1;}
  return 0;
}

int main(){
  int N;
  cin >> N;
  vector<int> H(N+1),D(N+1);
  for(int i=1;i<=N;i++){ cin >> H[i]; }
  for(int i=1;i<=N;i++){ cin >> D[i]; }

  vector<int> dp(N+1,1e9);
  dp[1]=f(H[1],D[1]);
  for(int i=2;i<=N;i++){
    int cf=f(H[i],D[i]);
    for(int j=i-2;j<=i-1;j++){
      dp[i]=min(dp[i],dp[j]+cf);
    }
  }
  cout << dp[N] << "\n";
  return 0;
}