本文共 1145 字，大约阅读时间需要 3 分钟。

链接：https://ac.nowcoder.com/acm/problem/15294

来源：牛客网

题目描述

有一只乌龟，初始在0的位置向右跑。 这只乌龟会依次接到一串指令，指令T表示向后转，指令F表示向前移动一个单位。乌龟不能忽视任何指令。 现在我们要修改其中正好n个指令（一个指令可以被改多次，一次修改定义为把某一个T变成F或把某一个F变成T）。 求这只乌龟在结束的时候离起点的最远距离。（假设乌龟最后的位置为x，我们想要abs(x)最大，输出最大的abs(x)） 输入描述: 第一行一个字符串c表示指令串。c只由F和T构成。 第二行一个整数n。 1 <= |c| <= 100, 1 <= n <= 50 输出描述: 一个数字表示答案。 示例1 输入 复制 FT 1 输出 复制 2 示例2 输入 复制 FFFTFFF 2 输出 复制 6 很好的一道记忆化搜索的题目。感觉记忆化搜索比dp好理解一些。 dp[i][fz][pos][dec]代表着到了第i个指令，还有fz次的反转机会，到了pos位置，方向是dec（0/1）。 具体解释看代码

#include
   
    #define ll long longusing namespace std;int dp[101][51][201][2];string s;int ans;int n;inline void dfs(int i,int fz,int pos,int dec){
   	if(i==s.size())//到达了指令的最末端。	{
   		if(fz==0) ans=max(ans,abs(pos));//必须执行了n次反转		return ;	}	if(fz<0||dp[i][fz][pos+100][dec]) return ;//如果没有反转次数了，或者这种情况已经出现过了。	dp[i][fz][pos+100][dec]=1;//这种情况标记为1。	if(s[i]=='F')	{
   		dfs(i+1,fz-1,pos,-1*dec);//用一次反转之后，方向变化，位置不变		dfs(i+1,fz,pos+dec,dec);//不用反转	}	else if(s[i]=='T')	{
   		dfs(i+1,fz-1,pos+dec,dec);//用了反转之后，方向不变，位置变化		dfs(i+1,fz,pos,dec*-1);//不要反转	}}int main(){
   	cin>>s;	cin>>n;	memset(dp,0,sizeof(dp));	ans=0;	dfs(0,n,0,1);	cout<
    
     <
    
   

努力加油a啊，(^o)/~

转载地址：http://yftvi.baihongyu.com/