【Luogu】 P8256 [NOI Online 2022 入门组] 字符串

点击打开链接

这道题一眼是个 d p dp dp 题 看到数据范围 n < = 400 n=1) dp[i][j][k]+=dp[i−1][j][k−1](k>=1) 即之后的操作需在后面删去 s i s_i si​ d p [ i ] [ d i g ] [ 0 ] + = d p [ i − 1 ] [ d i g − 1 ] [ 0 ] dp[i][dig][0]+=dp[i-1][dig-1][0] dp[i][dig][0]+=dp[i−1][dig−1][0] 即之后的操作需在前面删去 s i s_i si​ d p [ i ] [ j ] [ 0 ] + = d p [ i − 1 ] [ j ] [ 0 ] dp[i][j][0]+=dp[i-1][j][0] dp[i][j][0]+=dp[i−1][j][0] 即在后面加入 s i s_i si​ 注意从前面删和从后面删不一样 如果 s i = ′ − ′ s_i ='-' si​=′−′ d p [ i ] [ j ] [ k ] + = d p [ i − 1 ] [ j + 1 ] [ k ] + d p [ i − 1 ] [ j ] [ k + 1 ] dp[i][j][k]+=dp[i-1][j+1][k]+dp[i-1][j][k+1] dp[i][j][k]+=dp[i−1][j+1][k]+dp[i−1][j][k+1]，这没什么好解释的

最后的答案就是 d p [ n ] [ 0 ] [ 0 ] dp[n][0][0] dp[n][0][0]

这里需要特判一下最后 R R R 串的长度是否等于目标串的长度，不等于答案为 0 0 0，不然民间数据会 W A 20 p t s WA20pts WA20pts