牛客练习赛13 E-龟兔跑步

链接： https://www.nowcoder.com/acm/contest/70/E
来源：牛客网

题目描述

有一只乌龟，初始在0的位置向右跑。
这只乌龟会依次接到一串指令，指令T表示向后转，指令F表示向前移动一个单位。乌龟不能忽视任何指令。
现在我们要修改其中正好n个指令（一个指令可以被改多次，一次修改定义为把某一个T变成F或把某一个F变成T）。
求这只乌龟在结束的时候离起点的最远距离。（假设乌龟最后的位置为x，我们想要abs(x)最大，输出最大的abs(x)）

输入描述:

第一行一个字符串c表示指令串。c只由F和T构成。
第二行一个整数n。
1 <= |c| <= 100, 1 <= n <= 50

题解：
dfs遍历每一种可能。但如果不剪枝会超时，
可以用mp标记每一种状态，而状态最多不会超过一百万。
代码：

#include<bits/stdc++.h>
using namespace std;
char t[107];
bool mp[107][55][207][2];
int n,L,ma=0;
int abs1(int x)
{
    return x<0?-x:x;
}
void dfs(int step,int s,int x,int d)//操作次数，剩余修改次数，位置，方向
{
    if(s<0)return;
    int t1;if(d==-1)t1=0;else t1=1;
    if(mp[step][s][x+100][t1])return;//剪枝
    mp[step][s][x+100][t1]=1;
    if(step==L)
    {
        if(s%2==0) ma=max(ma,abs1(x));
        return;
    }
    if(t[step]=='T')
    {
        dfs(step+1,s-1,x+d,d);//修改此位置
        dfs(step+1,s,x,-d);//不修改此位置
    }
    else
    {
        dfs(step+1,s,x+d,d);
        dfs(step+1,s-1,x,-d);
    }
}
int main()
{
    scanf("%s%d",&t,&n);
    L=strlen(t);
    memset(mp,0,sizeof(mp));
    dfs(0,n,0,1);
    printf("%d\n",ma);
    return 0;
}