P2487 [SDOI2011]攔截導彈

求解二維上的LIS，并且要求出每個點的選中概率。

首先對于每個點的選中概率，可以通過方案數計算，那么就是選中它的方案數除以總方案數。關鍵在于選中它的方案數怎么求，可以通過以它開頭的LIS方案數和以它結束的LIS方案數進行計算。這個計算方法還是很巧妙的，相當于我們欽定了選擇它，然后向兩邊都是LIS。

然后就是一個典型的三維偏序了。

總結

以上是生活随笔為你收集整理的P2487 [SDOI2011]拦截导弹（cdq分治/计数问题思想）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。