1月31

今天還是看ac自動機的部落格，主要是看ac自動機加dp的題，ac自動機加矩陣的題也有很多，我沒看。ac自動機雖然可以與很多種dp相結合，但還是有規律可循的。加上dp的時候更換了模闆，不再用last數組優化了，而是将樹的很多節點連接配接起來，這裡不多說了。與機率dp相結合很容易看出來，因為有機率嗎，然後也是字元串與數比對的問題，這個倒是很容易判斷出來，這類題運用的是fill數組與建構的match數組，來進行點評。然後狀态壓縮的dp一般都是，字元串與字典集合之間比對有某種關系，然後進行狀态壓縮，然後進行dp在、，不過狀态壓縮的時候大佬亞的很玄學，感覺想不到。