P8194 [USACO22FEB] Phone Numbers P（dp）

panyf · 2022-03-11 14:53:59 · 题解

考虑从前到后 dp。当前 dp 了长度为 i 的前缀，记 f_{u_1,u_2,u_3,v_0,v_1,v_2,v_3} 表示第 i-2 位为 u_1，第 i-1 位为 u_2，第 i 位为 u_3,长度为 i-3 的前缀能否匹配（v_0=1 表示能匹配，v_0=0 表示不能），i-2 能否匹配，i-1 能否匹配，i 能否匹配。转移时枚举第 i+1 位的值，判断 [i-2,i+1],[i,i+1],[i+1,i+1] 这三个区间能否匹配。时间复杂度 O(n)。

算一下这个做法的常数，状态数 2^4\times 9^3，转移数 9。显然 TLE。

考虑优化。首先容易发现若 v_0=0，那么 u_1 就没用了，就不用记录了。若 v_0=v_1=0，那么 u_2 也就没用了。若 v_0=v_1=v_2=0，那么 u_3 也就没用了，若 v_0=v_1=v_2=v_3=0，那么这个状态不合法。但是 v_0=1 的时候还是要记 u_1,u_2,u_3，状态数只减少了不到一半。

若 v_0=1，但是 u_1,u_2,u_3 再加上任何一个数，都不能和 [i-2,i+1] 匹配上，那么可以把 v_0 改成 0。或者如果 [i-2,i+1] 的数不在一个正方形内，也可以把 v_0 改成 0。同理 v_1,v_2 也可以这样做。

加上这两个优化以后，再分析一下状态数。若 v_0=1，那么 u_1,u_2,u_3 一定是从数字串的区间 [i-2,i+1] 中选出三个数，有 24 种方案，并且 v_1 一定等于 0（因为），v_2,v_3 不确定，有 4\times 24=96 种方案。若 v_0=0,v_1=1，则 u_2,u_3 一定是 [i-1,i+2] 中选出的两个数，有 12 种方案，v_2,v_3 不确定，有 4\times 12=48 种方案。若 v_0=v_1=0,v_2=1，有 2\times 4=8 种方案。若 v_0=v_1=v_2=0,v_3=1，有 1 种方案。总状态数就是 96+48+8+1=153。实际上跑不满，按照官方题解的说法数据中状态不超过 50。可以写一个哈希表压缩状态。