首先這道題真的是個數(shù)位DP

我們考慮所有的限制：

首先第六個限制和第二個限制是重復的，保留第二個限制即可

第五個限制在轉(zhuǎn)移中可以判斷，不用放在狀態(tài)里

對于第一個限制，我們可以增加一維表示余數(shù)即可

對于第四個限制也是同理

對于第三個限制我們增加一維用0或1表示奇數(shù)或是偶數(shù)即可

對于第二個限制我們增加一維0/1/2/3表示匹配到第幾位即可

這樣我們算上位數(shù)一共五維做數(shù)位DP即可

如何計算平方和？

我們可以很輕松的求出[L,R]中滿足條件的個數(shù)記為s0

進而我們也可以很輕松的求出[L,R]中滿足條件的數(shù)的和記為s1

我們發(fā)現(xiàn)數(shù)位DP每次只轉(zhuǎn)移一位，那么我們只需要考慮這一位的貢獻即可

當前可表示為sigma((p*10^k+x)^2)

拆完后可得表示為sigma((p*10^k)^2)+sigma(2*p*10^k*x)+sigma(x^2)

這樣我們很容易通過s0’，s1'和s2‘轉(zhuǎn)移出來s0，s1,s2

?

最后的最后，要注意1314中有兩個1，所以在計算匹配長度的時候討論要細心一點

轉(zhuǎn)載于:https://www.cnblogs.com/joyouth/p/5479240.html

總結

以上是生活随笔為你收集整理的cojs 简单的数位DP 题解报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。