#36772: 從排列組合的角度看


harlivy_forever (噴火水雞肉飯)

學校 : 國立嘉義高級中學
編號 : 160563
來源 : [140.113.136.220]
最後登入時間 :
2024-11-19 20:59:13
d887. 1.山脈種類(chain) -- 99學年度台北市資訊學科能力競賽 | From: [220.143.11.88] | 發表日期 : 2023-08-07 23:49

 

 

令山坡向上和向下方別為矩陣(一個點,而非一格是一個空間)裡的向右和向下。因為山坡不可低於地平線,所以向下的次數必小於等於向上,等同於把矩陣所有滿足r=c的[r][c]連成一條線,只有直線右上半部(r<=c)是可以走的。和最常見的走捷徑問題一樣,因為到達每一點的方法皆是從該點左邊或上面那點,所以每點的方法數等於上面那點的方法數和左邊那點的方法數相加,前幾點的方法數如圖中所示。因最後會回到地平線(r=c),所求方法數便是直線r=c上的點的方法數。

 

 
ZeroJudge Forum