安置路灯（DP思路）
安置路灯
http://www.nowcoder.com/questionTerminal/3a3577b9d3294fb7845b96a9cd2e099c
题解
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;
}
}
投递字节跳动等公司10个岗位
查看11道真题和解析