51nod 1489 蜥蜴和地下室 dfs

蜥蜴和地下室 dfs"/>

51nod 1489 蜥蜴和地下室 dfs

题目链接：.html#!problemId=1489
题意：有一排怪物要打，可以使用一个对目标攻击能造成a点伤害的技能，并且能给旁边的怪物造成溅射伤害b点。左右两端点的怪物由于太远，无法直接攻击，只能通过溅射方式杀死，问最少使用多少技能，能使杀死所有怪物

#include<cstdio>
#include<queue>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<string>
#include<set>
#include<stack>
#include<algorithm>
#define cle(a) memset(a,0,sizeof(a))
#define inf(a) memset(a,ox3f,sizeof(a))
#define ll long long
#define Rep(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
const int INF = ( 2e9 ) + 2;
const int maxn = 20;
int H[maxn];
int n,a,b,ans;
void dfs(int N,int t)
{if(N==n){if(ans>t)ans=t;return ;}if(H[N-1]<0)    // 第N-1个被杀死 {dfs(N+1,t);}int t1=0;if(H[N-1]>=0){t1=H[N-1]/b+1;H[N-1]-=t1*b;H[N]-=t1*a;H[N+1]-=t1*b;dfs(N+1,t+t1);H[N-1]+=t1*b;H[N]+=t1*a;H[N+1]+=t1*b;}int t2=H[N]/a+1;if(H[N]>=0&&t2>t1)      // 直接杀死n需要t2次，在已经攻击了t1次的情况下（N-1已死） 杀死N可以选择 {                       //  直接t2次杀次，或者不用t2次杀死，在攻击N+1时用溅射的方式杀死  for(int i=t1+1;i<=t2;i++){H[N-1]-=i*b;H[N]-=i*a;H[N+1]-=i*b;dfs(N+1,t+i);H[N-1]+=i*b;H[N]+=i*a;H[N+1]+=i*b;}}
}
int main()
{scanf("%d%d%d",&n,&a,&b);for(int i=1;i<=n;i++)scanf("%d",&H[i]);  int c=H[1]/b+1;H[1]-=c*b;H[2]-=c*a;H[3]-=c*b;int t=c;if(H[n]>=0){int c=H[n]/b+1;H[n]-=c*b;H[n-1]-=c*a;H[n-2]-=c*b;t+=c;}ans=INF;dfs(2,0);if(ans==INF)ans=0;printf("%d\n",ans+t);
}