Hefei 2009 Problem H - Chinese Paper Cutting

Hefei 2009 Problem H AC 留念...
LOC ~= 280

---

題目大意（嚴謹細節略去）：
給一長方形紙張，T 個操作，操作分兩種：

1. 垂直／打橫對摺
2. 沿著某些連續的水平／垂直線段栽剪

在每個栽剪操作後，若果紙張被分為多個部份，只保留面積最大的部份。
在所有操作完成後，還原所有對摺操作。

求最終剩餘的紙張部份。

ICPC 2929 Hang or not to hang

題意：

給定一個 program（LOC ≤ 16）
有 ≤ 32 個 boolean variable（值 = 0 或 1）
instruction 有以下 10 種：

 
每個 instruction 執行時間花費 1 cycle（包括 STOP）

variable 的起始狀態是隨機的
問，程序最早結束時間可以是多少？
是否對任何起始狀態，都會「Loop死」？

---

枚舉全 2³² 種 variable 的起始狀態再逐一 simulate
顯然會超出 時間／memory 限制...

細心一想... 所謂 randomness 其實只是 JZ 指令

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 搜索