切換
舊版
前往
大廳
主題

ZeroJudge - e881: Q2 極限運動　解題心得

Not In My Back Yard | 2020-04-16 00:34:04 | 巴幣 0 | 人氣 245
題目連結：
題目大意：
第一列給定兩正整數 n 、m （2 ≦ n ≦ 1000 ， 1 ≦ m ≦ 10），代表有一個 n 道階梯的樓梯、多明哥最多一次可以跨 m 階。接著一列給定一非負整數 d （0 ≦ d ≦ 10），代表損壞了 d 個階梯。緊接著有 d 個由小排到大的正整數，代表損壞的 d 個階梯之編號（由低層到高層編號 1 ～ n）。

試問，多明哥從最底層（還沒踩上任何一階）到第 n 級階梯總共有多少方法數？

範例輸入：
範例輸入一：
3 2
0

範例輸入二：
8 2
1 5

範例輸入三：
101 10
0

範例輸出：
範例輸出一：
3

範例輸出二：
10

範例輸出三：
1211700015849788251502892752696
解題思維：
階梯問題的變體。如果該階梯是毀損的狀態，則在動態規劃求解時將其去除即可求出所求。

然後因為這題方法數可以很大，所以需要大數運算。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#動態規劃（Dynamic Programming）#大數
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

更多創作

追蹤 創作集
其他創作
作品資料夾