现在的位置: 首页 > 综合 > 正文

Codeforces 132C. Logo Turtle

2017年11月24日 ⁄ 综合 ⁄ 共 2145字 ⁄ 字号 评论关闭

枚举变换了几次,记忆化搜索

C. Logo Turtle
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A lot of people associate Logo programming language with turtle graphics. In this case the turtle moves along the straight line and accepts commands "T" ("turn
around") and "F" ("move 1 unit forward").

You are given a list of commands that will be given to the turtle. You have to change exactly n commands from the list (one command can be changed several
times). How far from the starting point can the turtle move after it follows all the commands of the modified list?

Input

The first line of input contains a string commands — the original list of commands. The string commands contains
between 1 and 100 characters, inclusive, and contains only characters "T" and "F".

The second line contains an integer n (1 ≤ n ≤ 50)
— the number of commands you have to change in the list.

Output

Output the maximum distance from the starting point to the ending point of the turtle's path. The ending point of the turtle's path is turtle's coordinate after it follows all the commands of the
modified list.

Sample test(s)
input
FT
1
output
2
input
FFFTFFF
2
output
6
Note

In the first example the best option is to change the second command ("T") to "F"
— this way the turtle will cover a distance of 2 units.

In the second example you have to change two commands. One of the ways to cover maximal distance of 6 units is to change the fourth command and first or last one.

/**
 * 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);
    }
}

抱歉!评论已关闭.