動態規劃

1/33ページ

漫畫:什麼是動態規劃?(整合版)

題目: 有一座高度是10級臺階的樓梯,從下往上走,每跨一步只能向上1級或者2級臺階。要求用程式來求出一共有多少種走法。 比如,每次走1級臺階,一共走10步,這是其中一種走法。我們可以簡寫成 1,1,1,1,1,1,1,1,1,1。 解法1:暴力列舉法(利用排列組合思想,寫一個多層巢狀迴圈遍歷出所有的 […]

灌溉機器人(狀壓dp)

題目描述 司令部的將軍們打算在N*M的網格地圖上部署他們的炮兵部隊。一個N*M的地圖由N行M列組成,地圖的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下圖。在每一格平原地形上最多可以佈置一支炮兵部隊(山地上不能夠部署炮兵部隊);一支炮兵部隊在地圖上的攻擊範圍如圖中黑色區域所示 […]

NOI 7627:雞蛋的硬度(dp)

總時間限制:  1000ms  記憶體限制:  65536kB 描述 最近XX公司舉辦了一個奇怪的比賽:雞蛋硬度之王爭霸賽。參賽者是來自世 界各地的母雞,比賽的內容是看誰下的蛋最硬,更奇怪的是XX公司並不使用什麼精密儀器來測量蛋的硬度,他們採用了一種最老土的辦法–從高度扔雞蛋– […]

NOI庫7627 雞蛋的硬度

題目:http://noi.openjudge.cn/ch0206/7627/ 分析:DP 1.先想一個簡單問題:只有兩個雞蛋的問題 兩個軟硬程度一樣但未知的雞蛋,它們有可能都在一樓就摔碎,也可能從一百層樓摔下來沒事。有座100層的建築,要你用這兩個雞蛋確定哪一層是雞蛋可以安全落下的最高位置。可以摔 […]

大樓扔雞蛋問題(動態規劃)

題目連結:poj 3783 題意分析: 經典題,紫書上的一道例題,4 2出了這道原題,我愣是以為是數學題,最後也沒做出來。題意是這樣的,給你N個雞蛋(硬度一樣),讓你測雞蛋的硬度,測量的方法就是從某棟M層的樓的某一層X上把雞蛋扔下來,如果雞蛋碎了,代表他的強度小於X;如果沒碎,則強度大於等於X。我們 […]

CSU暑期集訓day04_遞推_動態規劃_抽獎概率

題目: HDU 2006’10 ACM contest的頒獎晚會隆重開始了!  為了活躍氣氛,組織者舉行了一個別開生面、獎品豐厚的抽獎活動,這個活動的具體要求是這樣的:  首先,所有參加晚會的人員都將一張寫有自己名字的字條放入抽獎箱中;  然後,待所有字條加入完畢,每人從箱中取一個字條; […]