CFR 803 E. Roma and Poker ( DP )

Problem - E - Codeforces

題意：
你在玩遊戲，一場有三種結果，勝/平/敗。你知道當你的勝利的場數和敗北的場數的絕對差在 K 以上時，會立刻退出遊戲。現在你有一個序列描述 N 場遊戲，而你知道你打完這 N 場後退出。有些紀錄被塗成 '?'，要你復原出一個合理的模樣。若無解輸出 -1。

制約：
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 ] )