ZeroJudge 解題筆記：c560. SF 愛運動

作者：王一哲
日期：2025年8月17日


ZeroJudge 題目連結：c560. SF 愛運動

解題想法

用動態規畫解題，假設 $dp[i]$ 代表走到第 $i$ 階的方法數，走到第 1 階、1 種方法；走到第 2 階、1 種方法；走到第 3 階、2 種方法；走到第 4 階以上、$dp[i] = dp[i-1] + dp[i-3]$。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 18.1 MB，通過測試。

n, m = map(int, input().split())
ss = list(map(int, input().split()))
MOD = 1000000007
dp = [0]*(n+1)
dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 2
for i in range(4, n+1): dp[i] = (dp[i-1] + dp[i-3]) % MOD
now, ans = 0, 1
for s in ss:
    ans = (ans * dp[s-now]) % MOD
    now = s

ans = (ans * dp[n-now]) % MOD
print(ans)

C++ 程式碼

使用時間約為 17 ms，記憶體約為 1.1 MB，通過測試。

#include <iostream>
#define MOD 1000000007
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    LL n, m; cin >> n >> m;
    LL dp[n+1] = {0}; dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 2;
    for(LL i=4; i<=n; i++) dp[i] = (dp[i-1] + dp[i-3]) % MOD;
    LL now = 0, ans = 1, s;
    for(LL i=0; i<m; i++) {
        cin >> s;
        ans = (ans * dp[s-now]) % MOD;
        now = s;
    }
    ans = (ans * dp[n-now]) % MOD;
    cout << ans << "\n";
    return 0;
}