解析

先安利一波洛谷上我介紹如何用暴力日過去的博客
現在開始務正業
考慮把dp記錄狀態的一維s去掉
這樣單次轉移復雜度變成$n^3$
但是這樣顯然會算多啊！
因為一個編號可能會用很多次
考慮容斥
設$an{s}_i$表示至少浪費了i個編號的答案
那么我們的答案顯然就是
$$an{s}_0?an{s}_1+an{s}_2...$$
就是一個經典的利用容斥至少轉恰好的方法
至于ans的計算，可以暴力枚舉二進制的集合s，每次進行一次$n^3$轉移的計算
時間復雜度$O(n^3?2^n)$

暴力都日過去了就不貼代碼了

總結

以上是生活随笔為你收集整理的洛谷P3349：小星星（容斥dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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