2698 - 天天酷跑
实验闲暇之余，苏八八顺手玩儿起了天天酷跑。话说苏八八是个追求完美的好男人，今天他想知道如何跑才能得到最高的分数！
酷跑规则如下：
1、在一个一维的坐标轴上，人物从0点开始向正无穷方向移动，任务和道具均只会出现在整点上。
2、每个整点有高空，低空，地面3个位置。一般情况下人物在地面移动。如果在i点进行跳跃，则移动顺序为：i点的地面 ->i +1点的低空 -> i+2点的高空 -> i+3点的低空 -> i+4点的地面。
3、每个点高空，低空，地面都几种可能：’.’：空地、’#’：障碍、’1’-’9’：金币的价值。
4、人物必须从0开始连续地向正无穷方向移动，遇到金币可以获得相应分值，遇到障碍游戏结束，得分为0。
5、苏八八是特殊会员（RMB战士）在低空时也可以跳跃（跳跃轨迹同样遵循2，不会超出地图）！
Input
输入一个整数n (2<=n<=100000)表示起点到终点的距离。
下面3行每行n个字符，输入的字符只包含’.’、’1’-’9’、’#’。
（起点和终点保证全是’.’）
Output
输出一个整数表示跑到终点时的最高得分。若跑不到终点则得分为0。
Examples
Input
2 .. .. .. 3 .1. .2. .1. 7 .##3##. .#2#4#. .1###5. 7 .11311. .12141. .11115. 10 .#81#89#7. .864#5631. .38911763. 7 .##3##. .###4#. .1..5. 3 .#. .#. .#.
Output
0 2 15 48 15 6
Hint
第四个样例跳跃过程：’.88415937.’ = 48
Solution C++
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; #define N 100000+10 int dp[N][3], n; char mp[N][3],s[N]; void work(int prex, int prey, int nowx, int nowy){ if(mp[nowx][nowy] == '#') { dp[nowx][nowy] = 0; return ; } dp[nowx][nowy] = max(dp[nowx][nowy], dp[prex][prey]+mp[nowx][nowy]-'0'); } int main(){ int i, j; while(~scanf("%d",&n)){ for(i = 2; i >= 0; i--) { scanf("%s",s); for(j = 0; j < n; j++){mp[j][i] = s[j];if(mp[j][i]=='.')mp[j][i]='0';} } memset(dp, 0, sizeof dp); for(i = 1; i < n; i++) { if(mp[i-1][0]!='#') work(i-1,0, i,0); if(i-4>=0)//落地转移 { if(mp[i-4][0]!='#'&&mp[i-3][1]!='#'&&mp[i-2][2]!='#'&&mp[i-1][1]!='#') work(i-1,1, i,0); } if(mp[i-1][0]!='#')//起跳转移 work(i-1,0, i,1); if(i-3>=0)//落地转移 { if(mp[i-3][0]!='#'&&mp[i-2][1]!='#'&&mp[i-1][2]!='#') work(i-1,2, i,1); } if(i-2>=0) { if(mp[i-2][0]!='#'&&mp[i-1][1]!='#') work(i-1,1, i,2); } } int ans = 0; for(i = 0; i < 3; i++) ans = max(ans, dp[n-1][i]); printf("%d\n", ans); } return 0; }
Hint
第四个样例跳跃过程：’.88415937.’ = 48
