题解
f[i]: 前i条道路至少需要安置的路灯数
按照道理i的状态划分:
- 如果为X, 不需要照亮,f[i] = f[i-1]
- 如果为., 一个路灯可以照亮三个位置,f[i] = f[i - 3] + 1;
代码
#include <iostream> using namespace std; const int N = 1010; int n; int f[N]; // 到第i个至少需要摆放的路灯数 char w[N]; int main() { int T; cin >> T; while (T --) { cin >> n >> (w + 1); f[0] = 0; for (int i = 1; i <= n; i ++) { if (w[i] == 'X') f[i] = f[i - 1]; else f[i] = f[max(i - 3, 0)] + 1; } cout << f[n] << endl; } }