乌龟跑步.md

乌龟跑步

https://ac.nowcoder.com/acm/contest/70/E?&headNav=www&headNav=acm&headNav=acm

用dp[i][j][k][dir] 四个状态表示执行到第i个字符，用了j次操作，能否到达k，并朝向dir方向（dir只有两个取值，1表示正向，0表示反向）

dp = True表示能到达k，否则不能。当前状态能否true，要看当前状态（记为now）是否为true OR 上一个状态（记为last）是否为true（当前状态可能会比上一个状态提前计算出来，因为有多个状态转移，即now = now | last，用|=操作符可以简化为now =| last

初始dp = False，只有dp[0][0][100][1]=True，表示从100开始。最后分别计算正向和反向距初始点100的最远距离

py超时，但c++AC

import sys
s = sys.stdin.readline()[:-1]
n = int(input())

dp = [[[[False] * 2 for _ in range(210)] for _ in range(52)] for _ in range(101)]

s = ' ' + s	   #前面填空，从1开始
m = len(s)
dp[0][0][100][1]=True # 起始位置为100
for i in range(1, m):
    for j in range(n+1):
        for k in range(201):
            if s[i] == 'F':	   #前进指令
                dp[i][j][k+1][1] |= dp[i-1][j][k][1]    #直接向前（为何当前状态和上一个状态不用k和k-1表示？因为k>=0)
                dp[i][j][k][0] |= dp[i-1][j][k+1][0]    #直接向后
                if j > 0:
                    dp[i][j][k][1] |= dp[i-1][j-1][k][0]    #转向变向后
                    dp[i][j][k][0] |= dp[i-1][j-1][k][1]    #转向变向前
            else:	   #转向指令
                dp[i][j][k][1] |= dp[i-1][j][k][0]  #转向
                dp[i][j][k][0] |= dp[i-1][j][k][1]  #转向
                if j > 0:
                    dp[i][j][k+1][1] |= dp[i-1][j-1][k][1]   #转向变向前
                    dp[i][j][k][0] |= dp[i-1][j-1][k+1][0]   #转向变向后
ans = 0
for k in range(201):
    # 若能到达k处，由于起始从100出发，最远到达距离为与100的差值（大于100为正向，小于为反向）
    if dp[m-1][n][k][1]:
        ans = max(ans, abs(100-k))
    if dp[m-1][n][k][0]:
        ans = max(ans, abs(100-k))
print(ans)