哈利喜欢玩角色扮演的电脑游戏《蜥蜴和地下室》。此时，他正在扮演一个魔术师。在最后一关，他必须和一排的弓箭手战斗。他唯一能消灭他们的办法是一个火球咒语。如果哈利用他的火球咒语攻击第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 || DP
DFS:先把数组两端打爆，最开始思考DFS时，以每一次可以攻击除两端的任意元素来DFS，结果时间超限，然后不死心，开始剪枝，结果还有两组数据就是过不了。。然后又用BFS来写，结果爆空间。。。
然后看了这篇博客才搞定51nod 1489 蜥蜴和地下室(dfs or dp)，原来是我DFS的思路错了
首先把数组两端打爆，然后从左向右搜索，每次从当前元素到下一元素时，必须保证当前元素的前一元素以被打爆。
DFS:
#include<iostream> using namespace std; int n,a,b,ss=1e9; int d[15]; void DFS(int t,int s); int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>a>>b; for(int i=0;i<n;++i) cin>>d[i]; int ans=0,t; t=d[0]/b+1; ans+=t; d[0]=-1; d[1]-=a*t; d[2]-=b*t; if(d[n-1]>=0){ t=d[n-1]/b+1; ans+=t; d[n-1]=-1; d[n-2]-=a*t; d[n-3]-=b*t; } DFS(1,0); if(ss!=1e9) ans+=ss; cout<<ans<<endl; return 0; } void DFS(int t,int s) { int t1=0,t2=0; if(s>=ss) return; if(t==n){ if(s) ss=min(ss,s); return; } if(d[t-1]>=0) t1=d[t-1]/b+1; if(d[t]>=0) t2=d[t]/a+1; if(t1>t2){ //d[t]<d[t-1] d[t-1]-=b*t1; d[t]-=a*t1; d[t+1]-=b*t1; DFS(t+1,s+t1); d[t-1]+=b*t1; d[t]+=a*t1; d[t+1]+=b*t1; } for(int i=t1;i<=t2;++i) { d[t-1]-=b*i; d[t]-=a*i; d[t+1]-=b*i; DFS(t+1,s+i); d[t-1]+=b*i; d[t]+=a*i; d[t+1]+=b*i; } }
DP:
#include<iostream> #include<cstring> using namespace std; const int INF=1e9; const int MAX_N=20; int n,a,b; int d[MAX_N]; // dp[x][i][j][k]: 表示在x位置时，x-1，x，x+1位置的生命值分别从满血状态到i,j,k时候的最小攻击次数 int dp[MAX_N][MAX_N][MAX_N][MAX_N]; int main() { ios::sync_with_stdio(false); cin.tie(0); for(int t=0;t<MAX_N;++t) for(int i=0;i<MAX_N;++i) for(int j=0;j<MAX_N;++j) for(int k=0;k<MAX_N;++k) dp[t][i][j][k]=INF; cin>>n>>a>>b; for(int i=1;i<=n;++i) { cin>>d[i]; d[i]++; //保证为0的时候已被打爆 } dp[2][d[1]][d[2]][d[3]]=0; //满血状态的攻击次数为0 for(int t=2;t<n;++t) for(int i=d[t-1];i>=0;--i) for(int j=d[t];j>=0;--j) for(int k=d[t+1];k>=0;--k) { int ii=max(0,i-b); int jj=max(0,j-a); int kk=max(0,k-b); dp[t][ii][jj][kk]=min(dp[t][ii][jj][kk],dp[t][i][j][k]+1); if(!i) //可以攻击x+1位置来消灭x位置的敌人 dp[t+1][j][k][d[t+2]]=min(dp[t+1][j][k][d[t+2]],dp[t][i][j][k]); if(!ii) //可以攻击x+1位置来消灭x位置的敌人 dp[t+1][jj][kk][d[t+2]]=min(dp[t+1][jj][kk][d[t+2]],dp[t][ii][jj][kk]); } cout<<dp[n][0][0][0]<<endl; return 0; }
原文：https://www.cnblogs.com/davidxhc/p/12355694.html