枚举变换了几次,记忆化搜索
/** * Created by ckboss on 14-9-3. */ import java.util.*; public class O { static int len, n; static int[][][][] dp = new int[2][200][500][100]; ///base is 200; static boolean[][][][] vis = new boolean[2][200][500][100]; static String cmd; static int dfs(int dir, int cd, int pos, int cur) { if (cur < 0) return 0; if (cd == len) { if (cur > 0) return 0; else return Math.abs(pos - 200); } if (vis[dir][cd][pos][cur] == true) return dp[dir][cd][pos][cur]; int ret = 0; int mv = (dir == 1) ? -1 : 1; if (cmd.charAt(cd) == 'T') ret = Math.max(ret, Math.max(dfs(1 ^ dir, cd + 1, pos, cur), dfs(dir, cd + 1, pos + mv, cur - 1))); else if (cmd.charAt(cd) == 'F') ret = Math.max(ret, Math.max(dfs(dir, cd + 1, pos + mv, cur), dfs(1 ^ dir, cd + 1, pos, cur - 1))); vis[dir][cd][pos][cur] = true; dp[dir][cd][pos][cur] = ret; return ret; } public static void main(String[] args) { Scanner in = new Scanner(System.in); cmd = in.nextLine(); len = cmd.length(); n = in.nextInt(); int ans = -999999; for (int i = n; i >= 0; i -= 2) { ans = Math.max(ans, dfs(0, 0, 200, i)); } System.out.println(ans); } }