alan23273850 的刷題筆記
d624: 燈泡問題
Tags: dp
出處：https://zerojudge.tw/ShowProblem?problemid=d624
提交：https://zerojudge.tw/Submissions?problemid=d624&account=allllllan123456
問題：給你總共 $m\in[1,90]$ 秒燈泡的發亮/熄滅時間，並限定每一段連續熄滅的時間不可超過 $n\in[1,15]$ 秒。請問有多少種亮暗的組合能滿足這個總時間？
解法：這題還是經典 DP，但是稍為不直觀一點。我主要使用的方式是用全部減去不合法，看下面程式碼的註解，由前一組合法的方法數 dp[m-1] 的兩倍 (因為最新秒數可以是亮或暗) 可以得到目前不受限制的總方法數，但是有一種情況需要扣掉，就是最新秒數是暗的時候而且連前面的 n 秒燈泡也都是暗的，這樣是違反規定，只是要注意這樣子的方法數並不是 dp[m-n-1] 而是 dp[m-n-2]，因為包含在 dp[m-1] 的方法裡面最多只會有連續 n 秒燈泡是暗的，這暗示了再往前一秒 (m-n-1) 必須是亮的，所以還要再往前一秒 (m-n-2) 才會是自由秒數。另外在初始條件的部分，因為不論那顆必須發亮的燈泡 (m-n-1) 存不存在，都算是 1 種，所以要特別小心。
1#include <bits/stdc++.h>
2using namespace std;
3
4int n;
5long long dp[91];
6
7/* <----------- (m-1) ----------->O
8 * <----------- (m-1) ----------->X
9 * <--- (m-n-2) --->OXXX........XXX
10 * <---- n ---->
11 */
12long long f(int m) {
13 if (m < -1) return 0;
14 if (m <= 0) return 1;
15 if (dp[m]) return dp[m];
16 return dp[m] = 2 * f(m-1) - f(m-n-2);
17}
18
19int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
20 int m;
21 while (cin >> n >> m) {
22 memset(dp, 0, sizeof dp);
23 cout << f(m) << '\n';
24 }
25 return 0;
26}