安置路灯（DP思路）

题解

f[i]: 前i条道路至少需要安置的路灯数

按照道理i的状态划分：

1. 如果为X, 不需要照亮，f[i] = f[i-1]
2. 如果为., 一个路灯可以照亮三个位置，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;
    }
}