首页 > 代码库 > CF 132C Logo Turtle[dp+记忆化搜索]

CF 132C Logo Turtle[dp+记忆化搜索]

给出一串由FT构成的串,F代表前进,T代表转向,初始方向是1,转向后F由1变为-1(或者-1变成1)

例如FTFFFTFFFFF值为3

给出n,必须做n次操作(让F变为T或者让T变成F),求最远能离原来的地方前进多远(绝对值)


可以搜索来解决这个问题

对每次行程,我们可以选择

继续按当前方向走

或者改变方向

那么,粗略估算一下,字符串最长为100,那么就是2^100,复杂度过高


但是对于四个变量来说

当前方向,当前走了多远,在第几个行程,剩余操作数目

接下来所能走的的最远距离是确定的


那么可以记忆化搜索



#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
char str[111];
int dp[2][222][111][55];
int m;
int dfs(int dir,int pos,int i,int left){
	if(!str[i] && left) return 0;//行程完了操作数没用完不算,return 0
	if(dp[dir][pos+100][i][left]!=-1)	return dp[dir][pos+100][i][left];
	if(!str[i] && !left)	return dp[dir][pos+100][i][left]=abs(pos);//行程完了且操作数完了 则return pos
	int mv=(dir==1)?1:-1;
	if(left==0)    dp[dir][pos+100][i][left]=dfs(dir,pos+mv,i+1,left-(str[i]!='F'));//否则就继续按照当前方向走
	return dp[dir][pos+100][i][left]=max(dfs(dir,pos+mv,i+1,left-(str[i]!='F')),dfs(!dir,pos,i+1,left-(str[i]!='T')));
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("/home/rainto96/in.txt","r",stdin);
#endif

	memset(dp,-1,sizeof(dp));
	cin>>str>>m;
	int ans=0;
	for(int mm=m;mm>=0;mm-=2){
		ans=max(ans,dfs(1,0,0,mm));
		///cout<<"a::"<<ans<<endl;
		///cout<<mm<<endl;
	}
	cout<<ans<<endl;
	return 0;
}


CF 132C Logo Turtle[dp+记忆化搜索]