一区二区电影免费观看,欧美日韩精品一区二区,99精品视频免费观看视频

培訓作業-第六周（DP++<2>）

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

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

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

第4題代碼

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

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

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



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

c++&oi

培訓作業-第六周（DP++<2>）

導航

統計

常用鏈接

留言簿

隨筆檔案(57)

文章檔案(13)

搜索

最新評論

閱讀排行榜

評論排行榜