51nod 1489 蜥蜴和地下室(DFS)

51nod 1489 蜥蜴和地下室(DFS)

哈利喜欢玩角色扮演的电脑游戏《蜥蜴和地下室》。此时，他正在扮演一个魔术师。在最后一关，他必须和一排的弓箭手战斗。他唯一能消灭他们的办法是一个火球咒语。如果哈利用他的火球咒语攻击第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示例

3

这是一道DFS题，先要求出打完第一个和最后一个所用的火球术的个数。

在dfs所有的情况，每次到最后用Min去记录最小的耗费。

代码如下：

#include#include#include#includeusing namespace std;#define N 20#define inf 0xfffffffint h[N],res,n,a,b;int Min=inf;void DFS(int s,int cnt){ int i,x; if(s==n) {Min=min(cnt,Min); return ; } if(h[s-1]<0) DFS(s+1,cnt); x=0; if(h[s-1]>=0){ x=h[s-1]/b+1; h[s-1]-=x*b; h[s]-=x*a; h[s+1]-=x*b; DFS(s+1,cnt+x); h[s-1]+=x*b; h[s]+=x*a; h[s+1]+=x*b; } int y=h[s]/a+1; if(h[s]>=0&&y>x){ for(i=x+1;i<=y;i++){ h[s-1]-=i*b; h[s]-=i*a; h[s+1]-=i*b; DFS(s+1,cnt+i); h[s-1]+=i*b; h[s]+=i*a; h[s+1]+=i*b; } } return ;}int main(){ int k,i,j,m; memset(h,0,sizeof(h)); cin>>n>>a>>b; for(i=1;i<=n;i++){ cin>>h[i];} res=0; int x; x=h[1]/b+1; res+=x; h[1]-=x*b; h[2]-=x*a; h[3]-=x*b; if(h[n]>=0){ x=h[n]/b+1; res+=x; h[n]-=x*b; h[n-1]-=x*a; h[n-2]-=x*b; } DFS(2,0); if(Min==inf) Min=0; cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。