北市賽後首po,也是 HOJ 的首po。

接下來的 80 天應該不會碰coding了吧= =。

題目很簡潔,就是要你求 LIS 的個數。

可以先用 DP 把每個數字會放在 第幾個 位置做出來 (pos[N])。

對每個位置開一棵 BIT,再重做一次 LIS,同時計算出做到當前 x 有幾種可能 (cnt)。

也就是利用 BIT 把當前 x 所在位置 p,位置[p-1] 中所有比 x 小的數字的 cnt 加總,即為當前所有可能個數。

有點像 DP 的做完後,把 LIS 尾端的所有 cnt 加總就得到答案了。

因為記憶體的限制,所以我是直接開二維 vector,直接在 vector 弄 BIT= =。

我的code http://ideone.com/cIXjsu

p.s: 一直狂用 lower_bound XD。

 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言
  • jizz
  • 大牛!