HDU 6156 Palindrome Function 数位DP

 问题主要是求$k$进制下小于等于$n$的回文串的个数。

用$dp[base][start][cur]$表示在base进制下,从第start位开始填写,当前填到了第cur位,往后继续填能构成回文的方案数。如果填写的长度超过了一半,就不需要继续DFS了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注