将每一个接龙序列拼在一起,Li,RiL_i,R_iLi,Ri 表示此位置所属块的开始、结束。如果用 dp(r,i,1/0)dp(r,i,1/0)dp(r,i,1/0) 表示第 rrr 轮,第 iii 个位置采用 1/0 转移是否可行。
dp(r,i,0)=∨{j∈[Li,Ri]∩[i−k+1,i−1] ∣ dp(r,j)}dp(r,i,0)=\lor \{j\in [L_i,R_i]\cap [i-k+1,i-1]\ |\ dp(r,j)\}dp(r,i,0)=∨{j∈[Li,Ri]∩[i−k+1,i−1] ∣ dp(r,j)}
dp(r,i,1)=∨{j∈[1,Li−1]∪[Ri+1,∑l] ∣ dp(r−1,j)}dp(r,i,1)=\lor\{j\in [1,L_i-1]\cup [R_i+1,\sum l] \ |\ dp(r-1,j) \}dp(r,i,1)=∨{j∈[1,Li−1]∪[Ri+1,∑l] ∣ dp(r−1,j)}
这种想法还有救吗?是 O(Trik∑2l)O(Tr_ik\sum^2 l)O(Trik∑2l) 的。
目前没有想出太明确的优化方式。