萌新求助
查看原帖
萌新求助
766675
da_ke楼主2024/11/28 19:42

将每一个接龙序列拼在一起,Li,RiL_i,R_i 表示此位置所属块的开始、结束。如果用 dp(r,i,1/0)dp(r,i,1/0) 表示第 rr 轮,第 ii 个位置采用 1/0 转移是否可行。

dp(r,i,0)={j[Li,Ri][ik+1,i1]  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,1)={j[1,Li1][Ri+1,l]  dp(r1,j)}dp(r,i,1)=\lor\{j\in [1,L_i-1]\cup [R_i+1,\sum l] \ |\ dp(r-1,j) \}

这种想法还有救吗?是 O(Trik2l)O(Tr_ik\sum^2 l) 的。

目前没有想出太明确的优化方式。

2024/11/28 19:42
加载中...