# CFR 803 E. Roma and Poker ( DP )

Problem - E - Codeforces

The first line contains two numbers n (the length of Roma's sequence) and k (1 ≤ n, k ≤ 1000).
The second line contains the sequence s consisting of characters W, L, D and ?. There are exactly n characters in this sequence.

dp[ i ][ j ]: 已檢視前 i 個紀錄，現在勝利 - 失敗的場數是多少

O( N * K ) / O( N * K )

```N, K = map( int, input().split() )
S = input()

offset = K + 1
dp = [ [ False for i in range( offset * 2 ) ] for j in range( N + 1 ) ]
pre = [ [ 0 for i in range( offset * 2 ) ] for j in range( N + 1 ) ] # previous state
dp[ 0 ][ offset ] = True
for i in range( N ):
for j in range( offset * 2 ):
if not dp[ i ][ j ]: continue
if ( S[ i ] == 'W' or S[ i ] == '?' ) and not ( i + 1 < N and j + 1 >= offset + K ):
if not dp[ i + 1 ][ j + 1 ]:
dp[ i + 1 ][ j + 1 ] = True
pre[ i + 1 ][ j + 1 ] = j
if ( S[ i ] == 'L' or S[ i ] == '?' ) and not ( i + 1 < N and j - 1 <= offset - K ):
if not dp[ i + 1 ][ j - 1 ]:
dp[ i + 1 ][ j - 1 ] = True
pre[ i + 1 ][ j - 1 ] = j
if S[ i ] == 'D' or S[ i ] == '?':
if not dp[ i + 1 ][ j ]:
dp[ i + 1 ][ j ] = True
pre[ i + 1 ][ j ] = j

if not dp[ N ][ offset + K ] and not dp[ N ][ offset - K ]:
print( "NO" )
else:
ans = ""
i, j = N, offset + K if dp[ N ][ offset + K ] else offset - K
while i:
pj = pre[ i ][ j ]
if S[ i - 1 ] == '?':
if pj + 1 == j:
ans += "W"
elif pj - 1 == j:
ans += "L"
else:
ans += "D"
else:
ans += S[ i - 1 ]
i, j = i - 1, pj
print( ans[ : : -1 ] )
```