色综合久久久久综合99,2020最新久久久视精品爱,久久亚洲高清观看

培訓(xùn)作業(yè)-第六周（DP++<2>）

由于明天就要上下個星期一的課了，這個星期就算就此結(jié)束了。
總結(jié)一下，這個星期主要是完成一套DP練習(xí)題。4題150分鐘。
現(xiàn)場考的時候大悲劇245/400，據(jù)說省隊水平基本上是300+。
第一題釣魚各種邊界掛掉，WA了三個點。
第二題旅游路線唯一AC的一道題，樹形DP。
第三題 Ticket Office 覺得是O（n）DP但不會寫，于是貪心55/100
第四題廣場鋪磚狀態(tài)壓縮DP，竟然來不及思考了，果斷些了無解和n=2的情況，20/100.

第三題是ceoi2005的題，
貌似比原題簡單，我后來寫了一個顯然會漏解的DP 90/100
按照網(wǎng)上所說的貪心方法寫80/100，
仔細想想應(yīng)該是貪心+DP，但怎么調(diào)不是80就是90，于是放棄了
實在不值得。。。

第四題貌似當場有1h也想不出來。
一開始想的是用1表示橫放，2表示豎放，0表示被占據(jù)
后來發(fā)現(xiàn)雖然是O(3^n)的狀態(tài)數(shù)，但三進制不能操作，轉(zhuǎn)移必掛。
讓后又想出了記錄兩行的O(2^(2*n))的狀態(tài)數(shù)，
經(jīng)過dfs試驗只有10000多種狀態(tài)，雖然遠小于2^22但還是會掛。
于是終于才知道只要用一行的0/1儲存就行了，不過轉(zhuǎn)移時要順帶算出下一行的。
于是O（h*(2^(w))^2）算法形成了。
實現(xiàn)時用主動更新的方法。用DFS實現(xiàn)局部。

第4題代碼

后面到期中考試兩周基本上是連著的，一者要AC USACO，二者再順帶總結(jié)一下DP。

posted on 2012-03-30 23:28 zyn.cpp 閱讀(215) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

c++&oi

培訓(xùn)作業(yè)-第六周（DP++<2>）

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿

隨筆檔案(57)

文章檔案(13)

搜索

最新評論

閱讀排行榜

評論排行榜