Submission #1155874

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;
// template for creating 2d vector
template<typename T>
vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)
{ return vector< vector<T> >(rows, vector<T>(cols, init)); }



#define debug(x) cout << #x << "==" << x << endl;

const int inf = 100000000;

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

  vector<char> kukan(N+1);
  for(int i = 0; i < N; i++) { cin >> kukan[i]; }
  kukan[N] = '.';

  // dp[i] := i番目までの区間に到達するまでに踏む水たまりの最小数
  vector<int> dp(N+1);
  dp[0] = 0;
  for(int i = 1; i <= N; i++) {
    dp[i] = dp[i-1];
    if( i >= 2 ) dp[i] = min(dp[i],  dp[i-2]);
    if( i >= 3 ) dp[i] = min(dp[i],  dp[i-3]);
    if( kukan[i-1] == 'X' ) {
      dp[i] += 1;
    }
  }

  cout << dp[N] << "\n";

  return 0;
}

Submission Info

Judge Result