解法讨论
查看原帖
解法讨论
2673
abslime楼主2024/10/26 15:12

dp[i][j][t]表示第i轮能否能以第j个字符串的第t个位置开头(第2维和第3维总数不超过20万个状态)

每一轮dp[i][j][t]为true的话,就给第j个字符串区间[t+1,t+k-1]打一个加1标记(一维差分标记),表示可以以这个区间的字符结尾,然后再做一个前缀和扫一遍就可以知道每一个字符能不能走到

对于dp[i][...][...]到dp[i+1][...][...]的转移,需要像2020J方格取数那题一样,上下扫两遍

在扫描过程中维护辅助数组visd[j][x]表示第1~j个字符串是否可以走到数字x

visu[j][z]表示第j~n个字符串是否可以走到数字x

那么f[i+1][j][t]=visd[j-1][s[j][t]]||visu[j+1][s[j][t]]

上面的visu和visd是个数学记号便于理解,在代码实现时需要滚动数组优化掉

2024/10/26 15:12
加载中...