題目

哈利喜歡玩角色扮演的電腦游戲《蜥蜴和地下室》。此時，他正在扮演一個魔術師。在最后一關，他必須和一排的弓箭手戰斗。他唯一能消滅他們的辦法是一個火球咒語。如果哈利用他的火球咒語攻擊第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

輸出樣例

1

思路：首先利用殘余傷害將第 1、n 兩個人打死，然后進行 dfs，需要注意的是，在 dfs 的過程中要更新最小值，此外，弓箭手的生命等于 0 時仍視為存活，只有小于 0 時才死亡

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 100+5; const int dx[] = {-1,1,0,0}; const int dy[] = {0,0,-1,1}; using namespace std; int h[N]; int n,a,b; int cnt=INF; void dfs(int pos,int ans){if(pos==n){if(cnt>ans)cnt=ans;return;}if(h[pos-1]<0)//第pos-1個人死后向后搜索dfs(pos+1,ans);int num1=0;//殘余傷害殺死第pos-1個的次數if(h[pos-1]>=0){num1=h[pos-1]/b+1;h[pos-1]-=num1*b;h[pos]-=num1*a;h[pos+1]-=num1*b;dfs(pos+1,ans+num1);h[pos-1]+=num1*b;h[pos]+=num1*a;h[pos+1]+=num1*b;}int num2=h[pos]/a+1;//殺死第pos個的次數if(h[pos]>=0&&num1<num2){//第pos個沒有殺死且num1殺死的次數比num2次數多for(int i=num1+1;i<=num2;i++){//在num1到num2間枚舉次數h[pos-1]-=i*b;h[pos]-=i*a;h[pos+1]-=i*b;dfs(pos+1,ans+i);h[pos-1]+=i*b;h[pos]+=i*a;h[pos+1]+=i*b;}} }int main() {scanf("%d%d%d",&n,&a,&b);for(int i=1;i<=n;i++)scanf("%d",&h[i]);int res=0;int num;//打的次數num=h[1]/b+1;//殘余傷害打死第一個res+=num;h[1]-=num*b;//打第2個num次后第1個剩余的血量h[2]-=num*a;//打第2個num次后第2個剩余的血量h[3]-=num*b;//打第2個num次后第3個剩余的血量if(h[n]>=0){//最后一個沒有打死num=h[n]/b+1;//打第n-1個的次數res+=num;h[n]-=num*b;//打第n-1個num次后第n個剩余的血量h[n-1]-=num*a;//打第n-1個num次后第n-1個剩余的血量h[n-2]-=num*b;//打第n-1個num次后第n-2個剩余的血量}dfs(2,0);if(cnt!=INF)res+=cnt;printf("%d\n",res);return 0; }

?

總結

以上是生活随笔為你收集整理的蜥蜴与地下室（51Nod-1489）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。