本文主要是介绍51Nod_1489 蜥蜴和地下室【DFS】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
51Nod_1489 蜥蜴和地下室
http://www.51nod.com/Challenge/Problem.html#!#problemId=1489
题目
哈利喜欢玩角色扮演的电脑游戏《蜥蜴和地下室》。此时，他正在扮演一个魔术师。在最后一关，他必须和一排的弓箭手战斗。他唯一能消灭他们的办法是一个火球咒语。如果哈利用他的火球咒语攻击第i个弓箭手（他们从左到右标记），这个弓箭手会失去a点生命值。同时，这个咒语使与第i个弓箭手左右相邻的弓箭手（如果存在）分别失去b(1 ≤ b < a ≤ 10)点生命值。因为两个端点的弓箭手（即标记为1和n的弓箭手）与你相隔较远，所以火球不能直接攻击他们。但是哈利能用他的火球攻击其他任何弓箭手。每个弓箭手的生命值都已知。当一个弓箭手的生命值小于0时，这个弓箭手会死亡。请求出哈利杀死所有的敌人所需使用的最少的火球数。如果弓箭手已经死亡，哈利仍旧可以将他的火球扔向这个弓箭手。
输入
第一行包含3个整数 n, a, b (3 ≤ n ≤ 10; 1 ≤ b < a ≤ 10)，第二行包含n个整数——h1，h2，...，hn (1 ≤ hi ≤ 15)， hi 是第i个弓箭手所拥有的生命力。
输出
以一行输出t——所需要的最少的火球数。
样例输入
3 2 1
2 2 2样例输出
3分析
DFS。具体参见此博文
C++程序
#include<iostream>
#include<algorithm>using namespace std;const int INF=0x3f3f3f3f;
const int N=11;int ans=0;//消灭首尾需要的最少火球数
int ans2=INF;//消灭中间需要的最少火球数
int n,a,b;
int h[N];//生命值void dfs(int k,int num)
{//当到达第n个人时，更新结果，并返回 if(k==n){ans2=min(ans2,num);return;}//每次向后搜索都要保证第k-1个为负数if(h[k-1]<0){dfs(k+1,num);} int cnt1=0;//必须攻击k位置cnt1次，才能使得k-1为负数if(h[k-1]>=0){cnt1=h[k-1]/b+1;h[k-1]-=b*cnt1;h[k]-=a*cnt1;h[k+1]-=b*cnt1;dfs(k+1,num+cnt1);h[k-1]+=b*cnt1;h[k]+=a*cnt1;h[k+1]+=b*cnt1;}//只要保证cnt1~cnt2次都能保证第k-1个为负数int cnt2=h[k]/a+1;if(h[k]>=0&&cnt2>cnt1){for(int i=cnt1+1;i<=cnt2;i++){h[k-1]-=b*i;h[k]-=a*i;h[k+1]-=b*i;dfs(k+1,num+i);h[k-1]+=b*i;h[k]+=a*i;h[k+1]+=b*i; }}
} int main()
{scanf("%d%d%d",&n,&a,&b);for(int i=1;i<=n;i++)scanf("%d",&h[i]);//消灭第一个 int cnt=h[1]/b+1;ans+=cnt;h[1]-=b*cnt;h[2]-=a*cnt;h[3]-=b*cnt;//消灭最后一个if(h[n]>=0){cnt=h[n]/b+1;ans+=cnt;h[n]-=b*cnt;h[n-1]-=a*cnt;h[n-2]-=b*cnt;}dfs(2,0);printf("%d\n",ans+ans2);return 0;
}
这篇关于51Nod_1489 蜥蜴和地下室【DFS】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
