1489 蜥蜴和地下室

去掉头尾就可以吃了
dfs
AC代码：
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int INF=1<<30;
 5 int n,a,b,ans=INF,sum=0;
 6 int s[11];
 7 
 8 void dfs(int x,int num){
 9     if(x==n){
10         ans=min(ans,num);
11         return ;
12     }
13     if(s[x-1]<0){
14         dfs(x+1,num);
15     }
16     int t=0;
17     if(s[x-1]>=0){
18         t=s[x-1]/b+1;
19         num+=t;
20         s[x-1]-=b*t;
21         s[x]-=a*t;
22         s[x+1]-=b*t;
23         dfs(x+1,num);
24         num-=t;
25         s[x-1]+=b*t;
26         s[x]+=a*t;
27         s[x+1]+=b*t;
28     }
29     int t1=s[x]/a+1;//若x-1为负后x依然为正，则说明x血量大于x-1
30     //可以通过直接t1打爆x或通过x+1打爆x 
31     if(s[x]>=0&&t<t1){
32         for(int i=t=1;i<t1;i++){
33             num+=i;
34             s[x-1]-=b*i;
35             s[x]-=a*i;
36             s[x+1]-=b*i;
37             dfs(x+1,num);
38             num-=i;
39             s[x-1]+=b*i;
40             s[x]+=a*i;
41             s[x+1]+=b*i;
42         }
43     }
44     return ;
45 }
46 int main(){
47     cin>>n>>a>>b;
48     memset(s,0,sizeof(s));
49     for(int i=1;i<=n;i++){
50         cin>>s[i];
51     }
52     int x=s[1]/b+1;//去头 
53     sum+=x;
54     s[1]-=b*x;
55     s[2]-=a*x;
56     s[3]-=b*x;
57     if(s[n]>=0){//去尾，注意这里可能会受去头影响，所以设一个if 
58         x=s[n]/b+1;
59         sum+=x;
60         s[n]-=b*x;
61         s[n-1]-=a*x;
62         s[n-2]-=b*x;
63     }
64     dfs(2,0);
65     if(ans==INF)
66     ans=0;
67     cout<<sum+ans<<endl;
68     return 0;
69 }