题目在这里：点击打开链接

题意：

F表示前进一步，T表示变成反方向

给一串FT字符，和一个n，表示可以改变多少次，求可以走到的离原点最远的距离

改变就是F变成T、T变成F

关键：

dfs(int d,int pos,int i,int cnt)

dp[][][][] 依次表示，方向、最长距离、到字符串的哪一个点了、还剩多少改变次

因为你每到一步，下一步只有两种情况：

一种是方向改变，pos不变

一种个是方向不变，pos朝当前+1

两种情况的cnt 根据当前值是F还是T -0或者-1

哎╮(╯▽╰)╭我还是想不到这样定状态

感觉这样dfs里面dp的写法好奇怪。。但是自己不会写。。

参考别人那样写的。。好省代码

PS：

严重不爽！！

因为memset(dp,0,sizeof dp)一直超时！

memset(dp,-1,sizeof dp)就可以！

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<string>

using namespace std;

int dp[5][205][105][55],n;

char s[105];

int dfs(int d,int pos,int i,int cnt)

{

    if(cnt<0) return 0;

    if(i>=strlen(s)) return cnt>0?0:abs(pos);

    int &p=dp[d+1][pos+100][i][cnt];

    if(p!=-1) return p;

    p=max(dfs(d,pos+d,i+1,cnt-(s[i]!='F')),dfs((-1)*d,pos,i+1,cnt-(s[i]!='T')));

    return p;

}

int main()

{

    while(~scanf("%s%d",s,&n))

    {

        memset(dp,-1,sizeof dp);

        int ans=0;

        while(n>=0)//n剩偶数个的时候 可以在一位上改变都抵消掉

        {

            ans=max(ans,dfs(1,0,0,n));

            n-=2;

        }

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

    }

    return 0;

}