顯示包含「Searching」標籤的文章。顯示所有文章
顯示包含「Searching」標籤的文章。顯示所有文章

2010年6月25日星期五

PKU 3679 The Delivery of Control

題意:


給定 H x W 帶號整數二維陣列 (H, W ≤ 20)
現在要在其中走一個圈,周界 ≤ K (≤ 20)
(路線是 grid 的 edge,每走一條周界 += 1)
圈不可以 self-touch
計算被包圍的元素值的總和

求最大總和



不合法 shape 的樣例:


  • 需要連接
    • ◎ ◎
  • 不可以角碰角
    • ◎◎
      ◎ ◎
      ◎◎◎
    • 剛剛才想到:角碰角 ⇒ 有洞
      所以不需要另寫程序作處理
  • 不可以有洞 1 (周界 = 16)
    • ◎◎◎
      ◎ ◎
      ◎◎◎
  • 不可以有洞 2 (周界 = 20)
    • ◎◎◎
      ◎ ◎
      ◎ ◎
      ◎◎◎



昨晚(強迫)Leo 及 Chin 跟我討論這條比較少人AC 的題目

然後今天下午... 和 Joe 分別起手 code...
慶幸是挑戰成功了(雖然非常懷疑自己是水過)

嗯... 看見 range 及 10秒 時限 便想到 Searching 吧...

不過起初我還妄想能否用狀態 DP 解決
然後被一大堆不知怎麼處理的狀況解決了... orz
(當然,我不排除 DP 的可行性...)

所以只好 code 搜索

2010年6月16日星期三

[進階DP] 基於連通性狀態壓縮的動態規劃問題

看完 男人八題 的 題C:Tony's Tour 以後
[I like the title: "做男人不容易系列:是男人就过8题--LouTiancheng题"]

即時想起:
ICPC World Fianls 2010 - Problem I : Robots on Ice

\epsfbox{p4793.eps}



連結:
1) 《基于连通性状态压缩的动态规划问题》 By Cdq(陈丹琦)
  • 插頭 DP
  • 括號表示法(好似係)
  • Hamiltonian Path
似乎就係 exactly 老細想我地學既野...?

2) 【动态规划】Ural1519 Formula 1 - By ccy1991911
這是Google 返回的 Blog 文...
感覺寫的挺用心(未詳閱)

3) 【专辑】插头DP
NotOnlySuccess 寫的



插個花:
雖然自己都幾鐘意之前呢個黑底白字既 theme
而且感覺亦幾 Professional =v=
不過望落去時對眼真係有啲辛苦... 所以都係轉番白底黑字好啲

呀... 另外一個原因係 LaTeX 冇黑底白字(好似係)

呃... 暫時黎講個 blog 都仲係寫得冇乜系統
究竟寫 Technical Term 用中定英好呢?
白話文定書面語好呢?