UVA12825 - Happy Robot dp
浏览数：13 /
时间：2015年06月11日
题意：给定你机器的指令 L（左转） R（右转） F（直走） ？（前三项 未知），问你最终位置，x和y的范围/
解题思路： dp[i][j]{MINX，MINY，MAXX，MAXY} 表示 到了第i个指令，方向 为 j（1-4）的最值， DP即可 。
解题代码：
1 // File Name: d.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月21日 星期二 21时54分34秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define inf 1000000; 26 using namespace std; 27 char str[1004]; 28 int dp[1004][6][6]; 29 void print(int t) 30 { 31 for(int i = 1;i <= 4;i ++) 32 { 33 for(int j = 1;j <= 4;j ++) 34 printf("%d ",dp[t][i][j]); 35 printf("\n"); 36 } 37 printf("\n"); 38 } 39 void init(int t) 40 { 41 for(int i = 1;i <= 4 ;i ++) 42 for(int j = 1;j <= 4;j ++ ) 43 if(j == 1 || j == 3) 44 { 45 dp[t][i][j] = -inf; 46 }else { 47 dp[t][i][j] = inf; 48 } 49 } 50 int main(){ 51 int ca = 0 ; 52 while(scanf("%s",str) != EOF) 53 { 54 ca ++ ; 55 init(0); 56 for(int i = 1;i <= 4;i ++) 57 dp[0][1][i] = 0 ; 58 int len = strlen(str); 59 int t = 0 ; 60 //print(0); 61 for(int i = 0 ;i < len ;i ++) 62 { 63 if(str[i] == ‘R‘) 64 { 65 for(int j = 1 ; j <= 4;j ++) 66 memcpy(dp[t][j-1],dp[t][j],sizeof(dp[0][0])); 67 memcpy(dp[t][4],dp[t][0],sizeof(dp[0][0])); 68 }else if(str[i] == ‘L‘){ 69 for(int j = 4 ; j >= 1;j --) 70 memcpy(dp[t][j+1],dp[t][j],sizeof(dp[0][0])); 71 memcpy(dp[t][1],dp[t][5],sizeof(dp[0][0])); 72 }else if(str[i] == ‘F‘){ 73 for(int j = 1;j <= 4;j ++) 74 { 75 if(j == 1) 76 { 77 dp[t][j][1] ++; 78 dp[t][j][2] ++; 79 }else if(j == 2) 80 { 81 dp[t][j][3] ++; 82 dp[t][j][4] ++; 83 }else if(j == 3) 84 { 85 dp[t][j][1] --; 86 dp[t][j][2] --; 87 }else { 88 dp[t][j][3] --; 89 dp[t][j][4] --; 90 } 91 } 92 }else{ 93 t ++ ; 94 init(t); 95 int s1,s; 96 for(int j = 1;j <= 4 ;j ++) 97 { 98 int ne = (j == 4 ? 1:j + 1) ; 99 for(s = 1 ,s1 = 2; s <= 4l; s += 2, s1 += 2) 100 { 101 if(dp[t-1][j][s] > dp[t][ne][s]) 102 { 103 dp[t][ne][s] = dp[t-1][j][s]; 104 } 105 if(dp[t-1][j][s1] < dp[t][ne][s1]) 106 { 107 dp[t][ne][s1] = dp[t-1][j][s1]; 108 } 109 } 110 ne = (j == 1 ? 4:j - 1); 111 for(s = 1 ,s1 = 2; s <= 4; s += 2, s1 += 2) 112 { 113 if(dp[t-1][j][s] > dp[t][ne][s]) 114 { 115 dp[t][ne][s] = dp[t-1][j][s]; 116 } 117 if(dp[t-1][j][s1] < dp[t][ne][s1]) 118 { 119 dp[t][ne][s1] = dp[t-1][j][s1]; 120 } 121 } 122 123 } 124 for(int j = 1;j <= 4;j ++) 125 { 126 if(j == 1) 127 { 128 dp[t][j][1] = max(dp[t][j][1],dp[t-1][j][1] + 1); 129 dp[t][j][2] = min(dp[t][j][2],dp[t-1][j][2] + 1); 130 dp[t][j][3] = max(dp[t][j][3],dp[t-1][j][3] ); 131 dp[t][j][4] = min(dp[t][j][4],dp[t-1][j][4] ); 132 }else if(j == 2) 133 { 134 dp[t][j][1] = max(dp[t][j][1],dp[t-1][j][1]); 135 dp[t][j][2] = min(dp[t][j][2],dp[t-1][j][2]); 136 dp[t][j][3] = max(dp[t][j][3],dp[t-1][j][3] + 1); 137 dp[t][j][4] = min(dp[t][j][4],dp[t-1][j][4] + 1); 138 }else if(j == 3) 139 { 140 dp[t][j][1] = max(dp[t][j][1],dp[t-1][j][1] - 1); 141 dp[t][j][2] = min(dp[t][j][2],dp[t-1][j][2] - 1); 142 dp[t][j][3] = max(dp[t][j][3],dp[t-1][j][3] ); 143 dp[t][j][4] = min(dp[t][j][4],dp[t-1][j][4] ); 144 }else{ 145 dp[t][j][1] = max(dp[t][j][1],dp[t-1][j][1]); 146 dp[t][j][2] = min(dp[t][j][2],dp[t-1][j][2]); 147 dp[t][j][3] = max(dp[t][j][3],dp[t-1][j][3] - 1); 148 dp[t][j][4] = min(dp[t][j][4],dp[t-1][j][4] - 1); 149 } 150 } 151 } 152 153 //print(t); 154 } 155 int minx ,maxx,miny ,maxy; 156 minx = miny = inf; 157 maxx = maxy = -inf; 158 for(int j = 1;j <= 4;j ++) 159 { 160 if(dp[t][j][1] > maxx) 161 maxx = dp[t][j][1]; 162 if(dp[t][j][2] < minx) 163 minx = dp[t][j][2]; 164 if(dp[t][j][3] > maxy) 165 maxy = dp[t][j][3]; 166 if(dp[t][j][4] < miny) 167 miny = dp[t][j][4]; 168 } 169 printf("Case %d: %d %d %d %d\n",ca,minx,maxx,miny,maxy); 170 } 171 return 0; 172 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
