dp

1/26ページ

鏖戰字串

題目描述 Abwad在nbc即將完成她的程式的時候,急中生智拔掉了她電腦的電源線,爭取到了寶貴的時間。作為著名論文《論Ctrl-C與Ctrl-V在資訊學競賽中的應用》的作者,他巧妙地使用了這種上古祕術,順利扳回一城。 在決勝局中,Abwad決定和nbc鏖戰字串,比的是誰能更快地將一個“量子態的字串” […]

幫助Bsny

題目描述 Bsny的書架亂成一團了,幫他一下吧! 他的書架上一共有n本書,我們定義混亂值是連續相同高度書本的段數。例如,如果書的高度是30,30,31,31,32,那麼混亂值為3;30,32,32,31的混亂值也為3。但是31,32,31,32,31的混亂值為5,這實在是太亂了。 Bsny想儘可能減 […]

音樂

題目描述 邁克喜歡在火車旅行的時候用手機聽音樂,他有N首歌在手機裡,在整個火車途中,他可以聽P首歌,所以他想產生一個播放表產生P首歌曲,這個播放表的規則是: ·每首歌都要至少被播放一次 ·在兩首一樣的歌中間,至少有M首其他的歌 邁克在想有多少種不同的播放表可以產生,那麼給你N,M,P,你來算一下,輸 […]

工作安排

題目描述 眾所周知Kelukin是一名宇宙級土豪,他公司的生意自然是相當的好。 現在他手上有n份工作要完成,每一份工作有一個土豪指標Ak。由於這些工作數量太多,Kelukin又懶,所以他無法一個人完成,他需要僱用很多工人來幫忙。可是Kelukin十分小氣,經常剋扣工資,因此沒有多少人願意幫他。而願意 […]

HDU 2089不要62(數位DP)

Problem Description 杭州人稱那些傻乎乎粘嗒嗒的人為62(音:laoer)。 杭州交通管理局經常會擴充一些的士車牌照,新近出來一個好訊息,以後上牌照,不再含有不吉利的數字了,這樣一來,就可以消除個別的士司機和乘客的心理障礙,更安全地服務大眾。 不吉利的數字為所有含有4或62的號碼。 […]

灌溉機器人(狀壓dp)

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

動態規劃DP問題分類和經典題型

解題關鍵: 理解結構特徵,抽象出狀態,寫成狀態轉移方程。 動態規劃理念: 1.最優化原理    1951年美國數學家R.Bellman等人,根據一類多階段問題的特點,把多階段決策問題變換為一系列互相聯絡的單階段問題,然後逐個加以解決。一些靜態模型,只要人為地引進“時間”因素,分成 […]