【51Nod】1489 - 蜥蜴和地下室（dfs）

FishWang

发布于 2025-08-27 12:04:07

9200

代码可运行

运行总次数：0

代码可运行

题目链接：点击打开链接

1489 蜥蜴和地下室

题目来源： CodeForces

基准时间限制：1 秒空间限制：131072 KB 分值: 10 难度：2级算法题

关注

哈利喜欢玩角色扮演的电脑游戏《蜥蜴和地下室》。此时，他正在扮演一个魔术师。在最后一关，他必须和一排的弓箭手战斗。他唯一能消灭他们的办法是一个火球咒语。如果哈利用他的火球咒语攻击第i个弓箭手（他们从左到右标记），这个弓箭手会失去a点生命值。同时，这个咒语使与第i个弓箭手左右相邻的弓箭手（如果存在）分别失去b(1 ≤ b < a ≤ 10)点生命值。

因为两个端点的弓箭手（即标记为1和n的弓箭手）与你相隔较远，所以火球不能直接攻击他们。但是哈利能用他的火球攻击其他任何弓箭手。

每个弓箭手的生命值都已知。当一个弓箭手的生命值小于0时，这个弓箭手会死亡。请求出哈利杀死所有的敌人所需使用的最少的火球数。

如果弓箭手已经死亡，哈利仍旧可以将他的火球扔向这个弓箭手。

Input

第一行包含3个整数 n, a, b (3 ≤ n ≤ 10; 1 ≤ b < a ≤ 10)，第二行包含n个整数——h1，h2，...，hn (1 ≤ hi ≤ 15)， hi 是第i个弓箭手所拥有的生命力。

Output

以一行输出t——所需要的最少的火球数。

Input示例

3 2 1
2 2 2

Output示例

先灭掉最前和最后两个弓箭手，然后用dfs搜索。

向pos+1弓箭手搜索的条件是pos-1位置的弓箭手已经死亡。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int ans;
int n,a,b;
void dfs(int pos,int step,int hp[])
{
	if (pos == n-1)
	{
		if (hp[pos-1] >= 0 || hp[pos] >= 0)		//如果还需要攻击 
			step += max(hp[pos-1] / b , hp[pos] / a) + 1;
		ans = min(step , ans);
		return;
	}
	while (hp[pos-1] >= 0 || hp[pos] >= 0)
	{
		if (hp[pos-1] < 0)		//前面的弓箭手死亡，就可以继续搜索了 
		{
			int p[10];
			for (int i = 0 ; i < n ; i++)
				p[i] = hp[i];
			dfs(pos+1,step,p);		//递归搜索 
		}
		hp[pos-1] -= b;
		hp[pos] -= a;
		hp[pos+1] -= b;
		step++;
	}
	int p[10];
	for (int i = 0 ; i < n ; i++)
		p[i] = hp[i];
	dfs(pos+1,step,p);		//都小于0的时候再搜索下一个 
}
int main()
{
	int step,res;
	int hp[10];
	scanf ("%d %d %d",&n,&a,&b);
	for (int i = 0 ; i < n ; i++)
		scanf ("%d",&hp[i]);
	res = 0;
	//先溅射打死第一个 
	step = hp[0] / b + 1;
	hp[0] -= b * step;
	hp[1] -= a * step;
	hp[2] -= b * step;
	res += step;
	//再溅射打死最后一个
	if (hp[n-1] >= 0)
	{
		step = hp[n-1] / b + 1;
		hp[n-1] -= b * step;
		hp[n-2] -= a * step;
		hp[n-3] -= b * step;
		res += step;
	}
	//然后dfs把剩下的都杀死需要的最小次数
	ans = INF;
	n--;
	dfs(1,0,hp);		//从第2个开始dfs 
	printf ("%d\n",ans + res);
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

搜索