湖南14年省赛 H - Happy Robot dp

本文主要是介绍湖南14年省赛 H - Happy Robot dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A robot is moving from (0,0) according to a command sequence. Each character in the sequence is
command:
• L: turn left
• R: turn right
• F: go forward one step
Interestingly, the command sequence contains some wildcard character ‘?’. The robot can treat it
any one of L, R or F at its own wish, which makes it really happy.
Let (x, y) be the final position of the robot, your task is to find out the minimal/maximal possible
value of x and y. Initially the robot is facing east (i.e. facing (1,0) in Cartesian coordinate system).
After a left turn it will face north (i.e. facing (0,1)).
Input
There will be at most 1000 test cases. Each case contains a command sequence with no more than
1000 characters.
Output
For each test case, print the case number, followed by minimal/maximal possible x (in this order), then
the minimal/maximal possible y.


Sample Input


F?F
L??
LFFFRF


Sample Output


Case 1: 1 3 -1 1
Case 2: -1 1 0 2

Case 3: 1 1 3 3

题意：

给出一串字符，有三种操作：左转，右转，直走一步

问号代表上面三种的某一种

四次dp

分别计算走动过程中 x  y 的可以到达的最大最小

四种情况其实差不多

定义四个方向

0   代表    东

1   代表    北

2   代表    西

3   代表    南

这些方向都可以随意定

因为刚开始都是面朝东，那么

dp[ 0 ][ 0 ] =0;

dp[ 0 ][ 1 ] =INF

dp[ 0 ][ 2 ] =INF

dp[ 0 ][ 3 ] =INF

这里对于转向的操作需要注意理解

具体见代码中的左转右转函数

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define maxn 1010
#define INF 0x3f3f3f3f
int dp[maxn][5];
char a[maxn];void turn_left(int i)
{dp[i+1][0]=dp[i][3];dp[i+1][3]=dp[i][2];dp[i+1][2]=dp[i][1];dp[i+1][1]=dp[i][0];
}void turn_right(int i)
{dp[i+1][3]=dp[i][0];dp[i+1][0]=dp[i][1];dp[i+1][1]=dp[i][2];dp[i+1][2]=dp[i][3];
}int main()
{int cnt=1,len,i;//freopen("in.txt","r",stdin);while(scanf("%s",a)!=EOF){int xmax=-INF;int xmin=INF;int ymax=-INF;int ymin=INF;len=strlen(a);//--------------------------求x最大--------------------------------//dp[0][0]=0;dp[0][1]=-INF;dp[0][2]=-INF;dp[0][3]=-INF;for(i=0;i<len;i++){if(a[i]=='F'){dp[i+1][0]=dp[i][0]+1;dp[i+1][1]=dp[i][1];dp[i+1][2]=dp[i][2]-1;dp[i+1][3]=dp[i][3];}else if(a[i]=='L')turn_left(i);else if(a[i]=='R')turn_right(i);else{dp[i+1][0]=max(dp[i][0]+1,max(dp[i][1],dp[i][3]));dp[i+1][1]=max(dp[i][1],max(dp[i][2],dp[i][0]));dp[i+1][2]=max(dp[i][2]-1,max(dp[i][1],dp[i][3]));dp[i+1][3]=max(dp[i][3],max(dp[i][2],dp[i][0]));}}xmax=max(xmax,dp[len][0]);xmax=max(xmax,dp[len][1]);xmax=max(xmax,dp[len][2]);xmax=max(xmax,dp[len][3]);//--------------------------求x最小--------------------------------//dp[0][0]=0;dp[0][1]=INF;dp[0][2]=INF;dp[0][3]=INF;for(i=0;i<len;i++){if(a[i]=='F'){dp[i+1][0]=dp[i][0]+1;dp[i+1][1]=dp[i][1];dp[i+1][2]=dp[i][2]-1;dp[i+1][3]=dp[i][3];}else if(a[i]=='L')turn_left(i);else if(a[i]=='R')turn_right(i);else{dp[i+1][0]=min(dp[i][0]+1,min(dp[i][1],dp[i][3]));dp[i+1][1]=min(dp[i][1],min(dp[i][2],dp[i][0]));dp[i+1][2]=min(dp[i][2]-1,min(dp[i][1],dp[i][3]));dp[i+1][3]=min(dp[i][3],min(dp[i][2],dp[i][0]));}}xmin=min(xmin,dp[len][0]);xmin=min(xmin,dp[len][1]);xmin=min(xmin,dp[len][2]);xmin=min(xmin,dp[len][3]);//--------------------------求y最大--------------------------------//dp[0][0]=0;dp[0][1]=-INF;dp[0][2]=-INF;dp[0][3]=-INF;for(i=0;i<len;i++){if(a[i]=='F'){dp[i+1][0]=dp[i][0];dp[i+1][1]=dp[i][1]+1;dp[i+1][2]=dp[i][2];dp[i+1][3]=dp[i][3]-1;}else if(a[i]=='L')turn_left(i);else if(a[i]=='R')turn_right(i);else{dp[i+1][0]=max(dp[i][0],max(dp[i][1],dp[i][3]));dp[i+1][1]=max(dp[i][1]+1,max(dp[i][2],dp[i][0]));dp[i+1][2]=max(dp[i][2],max(dp[i][1],dp[i][3]));dp[i+1][3]=max(dp[i][3]-1,max(dp[i][2],dp[i][0]));}}ymax=max(ymax,dp[len][0]);ymax=max(ymax,dp[len][1]);ymax=max(ymax,dp[len][2]);ymax=max(ymax,dp[len][3]);//--------------------------求y最小--------------------------------//dp[0][0]=0;dp[0][1]=INF;dp[0][2]=INF;dp[0][3]=INF;for(i=0;i<len;i++){if(a[i]=='F'){dp[i+1][0]=dp[i][0];dp[i+1][1]=dp[i][1]+1;dp[i+1][2]=dp[i][2];dp[i+1][3]=dp[i][3]-1;}else if(a[i]=='L')turn_left(i);else if(a[i]=='R')turn_right(i);else{dp[i+1][0]=min(dp[i][0],min(dp[i][1],dp[i][3]));dp[i+1][1]=min(dp[i][1]+1,min(dp[i][2],dp[i][0]));dp[i+1][2]=min(dp[i][2],min(dp[i][1],dp[i][3]));dp[i+1][3]=min(dp[i][3]-1,min(dp[i][2],dp[i][0]));}}ymin=min(ymin,dp[len][0]);ymin=min(ymin,dp[len][1]);ymin=min(ymin,dp[len][2]);ymin=min(ymin,dp[len][3]);printf("Case %d: %d %d %d %d\n",cnt++,xmin,xmax,ymin,ymax);}return 0;
}

这篇关于湖南14年省赛 H - Happy Robot dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---