alan23273850 的刷題筆記
d916: 4. 高空煙火時間限制
Tags: dp
出處：https://zerojudge.tw/ShowProblem?problemid=d916
提交：https://zerojudge.tw/Submissions?problemid=d916&account=allllllan123456
問題：給定僅包含單色與彩色的煙火總長度 $N\in[2,3000]$，以及限制兩相鄰彩色煙火之間至少須包含 $M\in[1,N)$ 個單色煙火。請問有多少種組合能滿足此總長度？
解法：這題也是經典 DP，而且也不難想。如果最後一個點是單色，那麼前一個點無限制；如果最後一個點是彩色，那麼前 M 個點都必須是單色，要等到第前 M+1 個點開始才無限制，所以 dp[n] = dp[n-1] + dp[n-m-1]，最後只要注意一下初始條件就好。而且這題很貼心已經自動幫我們 mod 10000 了，所以毋須考慮大數加法的實作。
1#include <bits/stdc++.h>
2using namespace std;
3
4int m, dp[3001];
5
6int f(int n) {
7 if (n < 1) return 0;
8 if (n <= m+1) return n+1;
9 if (dp[n]) return dp[n];
10 return dp[n] = (f(n-1) + f(n-m-1)) % 10000;
11}
12
13int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
14 int n;
15 while (cin >> n >> m) {
16 memset(dp, 0, sizeof dp);
17 cout << f(n) << '\n';
18 }
19 return 0;
20}