P2481 [SDOI2010] 代码拍卖会

数位 DP

设:

  • dp[len][last][rem]
  • last:目前最后一只猪的出价,范围 1..9
  • rem:目前构成的 len 位数除以 P 的余数

若在右边加入数字 x,必须满足 x >= last,新余数是:

$newRem=(rem\times 10+x)\bmod P$