CodeForces 132C Logo Turtle (记忆化搜索)

时间：2022-06-11 00:04:17

Description

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 Input

Input
FT 1
Output
2
Input
FFFTFFF 2
Output
6

Hint

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.

题解：给一个序列，有TF，F代表机器人向前走一步，T代表机器人转身，再给你一个N问改变N个字母后机器人最多可以走多远，每个字母可以改变多次；刚开始写了下没用记忆化搜索果断超时了，而且还不知道怎么把一个字母改变多次，然后看了下大神的写法，加个数组记忆下就好了，关于字母可以改变多次，直接循环N，N-=2就好了；

dp[2][MAXN<<1][MAXN][50]，MAXN<<1是因为当前位置可能为负数；

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<map>

#include<string>

using namespace std;

const int INF=0x3f3f3f3f;

#define SI(x) scanf("%d",&x)

#define PI(x) printf("%d",x)

#define P_ printf(" ")

#define mem(x,y) memset(x,y,sizeof(x))

const int MAXN=;

char s[MAXN];

int dp[][MAXN<<][MAXN][];

int dfs(int fw,int pos,int l,int n){

    if(n<)return ;

    if(!s[pos])

        return n>?:abs(l);

    if(dp[fw][l+][pos][n]!=-)return dp[fw][l+][pos][n];

    return dp[fw][l+][pos][n]=max(dfs(fw,pos+,fw?l+:l-,n-(s[pos]=='T')),dfs(-fw,pos+,l,n-(s[pos]=='F')));

}

int main(){

    int n;

    while(~scanf("%s",s)){

        SI(n);

        mem(dp,-);

        int ans=;

        for(;n>=;n-=)ans=max(ans,dfs(,,,n));

        printf("%d\n",ans);

    }

    return ;

}

相关文章