回到首頁 |切換到寬版

登入加入我們找回密碼切換風格

竹園論壇»論壇 › 學生社團 › 台南一中資訊社 › 解題分享 › d887 - 1.山脈種類(chain)

發新帖

查看: 1587|回復: 3

上一主題

下一主題

[ZJ] d887 - 1.山脈種類(chain)

TA的每日心情

	開心 2015-4-12 10:09

簽到天數: 137 天

[LV.7]常住居民III

142 主題	686 帖子	3559 積分

蘇多門

Rank: 8 Rank: 8

積分: 3559

發消息

電梯直達

跳轉到指定樓層

樓主

發表於 2014-8-7 20:54:43 | 只看該作者回帖獎勵

回帖獎勵

|倒序瀏覽 |閱讀模式

趕快加入我們來參與討論吧！

您需要登錄才可以下載或查看，沒有帳號？加入我們

x

本帖最後由 domen111 於 2014-8-7 20:58 編輯

http://zerojudge.tw/ShowProblem?problemid=d887
既然有人問那就發一下解題分享吧!

dp[ i][j]: i代表第幾步，j代表高度，dp[ i][j]代表走到此點的方法數，如圖

稍微思考一下，發現dp[ i][j]=dp[i-1][j-1]+dp[i-1][j+1]，就是把可以走到(i,j)的點的方法數相加。

可以分成兩半處理，用到中間點的方法數相乘就可以了(詳情見程式碼)

AC code: http://ideone.com/MfI3rx

點評

你果然比較會DP OAO 發表於 2014-8-7 22:16

這題標準的"卡特蘭數" 發表於 2014-8-7 22:13

那個"[i]"很容易爛掉，有沒有甚麼方法可以處理? 發表於 2014-8-7 20:59

收藏0 支持0 反對0 分享

蘇多門 domen111
My Web: https://sites.google.com/site/domenprg/

回復

使用道具檢舉

發新帖

小黑屋|手機版|精簡版|竹園論壇

Powered by Discuz! X3.2© 2001-2013 Comsenz Inc. Skin by 恩斯道 Develop by Sylveon. 全站文章授權：
本著作係採用創用 CC 姓名標示-非商業性-相同方式分享 4.0 國際授權條款授權.

GMT+8, 2024-5-5 17:23

快速回覆 返回頂部 返回列表