本文主要是介绍codeforces 132C Logo Turtle--- dp dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目在这里：点击打开链接
题意：
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;
}
这篇关于codeforces 132C Logo Turtle--- dp dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
