首页 > 代码库 > CSU 1510 Happy Robot
CSU 1510 Happy Robot
1510: Happy Robot
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 19 Solved: 7
Description
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?FL??LFFFRFSample Output
Case 1: 1 3 -1 1Case 2: -1 1 0 2Case 3: 1 1 3 3HINT
Source
湖南省第十届大学生计算机程序设计竞赛
解题：dp啦，现场居然没做出来。。。笨得还可以。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 1010;18 char cmd[maxn];19 int dp[2][4];20 const int dir[4][2] = {1,0,0,-1,-1,0,0,1};//右 下 左 上21 int mymax(int a,int b){22 return max(a,b);23 }24 int mymin(int a,int b){25 return min(a,b);26 }27 int go(int (*op)(int,int),bool flag,int x,int y){28 int cur = 0;29 dp[0][0] = 0;30 for(int i = 1; i < 4; ++i)31 if(flag) dp[0][i] = -INF;32 else dp[0][i] = INF;33 for(int i = 0; cmd[i]; ++i) {34 for(int k = 0; k < 4; ++k) dp[cur^1][k] = flag?-INF:INF;35 if(cmd[i] == ‘F‘ || cmd[i] == ‘?‘) {36 dp[cur^1][0] = op(dp[cur^1][0],dp[cur][0]+x);37 dp[cur^1][1] = op(dp[cur^1][1],dp[cur][1]-y);38 dp[cur^1][2] = op(dp[cur^1][2],dp[cur][2]-x);39 dp[cur^1][3] = op(dp[cur^1][3],dp[cur][3]+y);40 }41 if(cmd[i] == ‘L‘ || cmd[i] == ‘?‘) {42 dp[cur^1][0] = op(dp[cur^1][0],dp[cur][1]);43 dp[cur^1][1] = op(dp[cur^1][1],dp[cur][2]);44 dp[cur^1][2] = op(dp[cur^1][2],dp[cur][3]);45 dp[cur^1][3] = op(dp[cur^1][3],dp[cur][0]);46 }47 if(cmd[i] == ‘R‘ || cmd[i] == ‘?‘) {48 dp[cur^1][0] = op(dp[cur^1][0],dp[cur][3]);49 dp[cur^1][1] = op(dp[cur^1][1],dp[cur][0]);50 dp[cur^1][2] = op(dp[cur^1][2],dp[cur][1]);51 dp[cur^1][3] = op(dp[cur^1][3],dp[cur][2]);52 }53 cur ^= 1;54 }55 int ans = flag?-INF:INF;56 for(int i = 0; i < 4; ++i)57 ans = op(dp[cur][i],ans);58 return ans;59 }60 int main() {61 int cs = 1;62 while(~scanf("%s",cmd)) {63 int max_x = go(mymax,true,1,0);64 int min_x = go(mymin,false,1,0);65 int max_y = go(mymax,true,0,1);66 int min_y = go(mymin,false,0,1);67 printf("Case %d: %d %d %d %d\n",cs++,min_x,max_x,min_y,max_y);68 }69 return 0;70 }
CSU 1510 Happy Robot
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。