alan23273850 的刷題筆記
d702: SOS
Tags: big-number, dp
出處：https://zerojudge.tw/ShowProblem?problemid=d702
提交：https://zerojudge.tw/Submissions?problemid=d702&account=allllllan123456
問題：指定一組哨音總長度 $n\in[1,1000]$ 秒，每個短音持續 1 秒，每個長音持續 2 秒，兩哨音中間休息 1 秒鐘，而且第一秒與最後一秒都不是休息秒。請問有多少種組合能滿足此總長度？
解法：這題也是經典 DP，而且蠻好想的，如果最後一秒鐘是短音，那麼考量到休息秒，要往前推 2 秒才會繼續有哨音；如果最後一秒鐘是長音，也要考量到休息秒，要往前推 3 秒才會繼續有哨音，所以 dp[n] = dp[n-2] + dp[n-3]，最後只要注意一下初始條件就好。另外這題因為答案很大，還需要用到大數加法的技巧，程式碼中也有實作。
1#include <bits/stdc++.h>
2using namespace std;
3
4int length[1001], dp[1001][14]; // 14 * 9 = 126 > 125
5
6int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
7 for (int i=1; i<=3; i++) { length[i] = dp[i][0] = 1; }
8 for (int i=4; i<=1000; i++) {
9 for (int j=0; j<length[i-2]; j++) { // assume length[i-2] >= length[i-3]
10 dp[i][j] += dp[i-2][j] + dp[i-3][j];
11 dp[i][j+1] += dp[i][j] / 1000000000;
12 dp[i][j] %= 1000000000;
13 }
14 length[i] = length[i-2] + (dp[i][length[i-2]] > 0);
15 } int n;
16 while (cin >> n) {
17 cout << dp[n][length[n]-1];
18 for (int i=length[n]-2; i>=0; i--)
19 cout << setfill('0') << setw(9) << dp[n][i];
20 cout << '\n';
21 }
22 return 0;
23}