游客 注册 | 登录
中文 | En

2698 - 天天酷跑

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

实验闲暇之余，苏八八顺手玩儿起了天天酷跑。话说苏八八是个追求完美的好男人，今天他想知道如何跑才能得到最高的分数！

酷跑规则如下：

1、在一个一维的坐标轴上，人物从0点开始向正无穷方向移动，任务和道具均只会出现在整点上。

2、每个整点有高空，低空，地面3个位置。一般情况下人物在地面移动。如果在i点进行跳跃，则移动顺序为：i点的地面 ->i +1点的低空 -> i+2点的高空       -> i+3点的低空 -> i+4点的地面。

3、每个点高空，低空，地面都几种可能：’.’：空地、’#’：障碍、’1’-’9’：金币的价值。

4、人物必须从0开始连续地向正无穷方向移动，遇到金币可以获得相应分值，遇到障碍游戏结束，得分为0。

5、苏八八是特殊会员（RMB战士）在低空时也可以跳跃（跳跃轨迹同样遵循2，不会超出地图）！

题目输入

输入一个整数n (2<=n<=100000)表示起点到终点的距离。

下面3行每行n个字符，输入的字符只包含’.’、’1’-’9’、’#’。

（起点和终点保证全是’.’）

题目输出

输出一个整数表示跑到终点时的最高得分。若跑不到终点则得分为0。

输入/输出样例

输入格式

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
.#.
.#.
.#.

输出格式

0
2
15
48
15
6

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;
}
请先登陆