1489 蜥蜴和地下室+bfs

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1489
题目大意：输入第一行包含3个整数 n, a, b
第二行输入n只蜥蜴的生命值，你可以选择编号为2~n的任意第i只蜥蜴进行火球术，对第i只蜥蜴造成a点伤害，对左右的蜥蜴造成b点伤害，当生命值<0时蜥蜴死亡（巨坑），但可以继续攻击，求杀死全部蜥蜴的最小攻击次数。

n和hi的范围都比较小，考虑dfs。
当是纯dfs会爆，所以还要有策略的dfs。

因为这道题有点和poj那个熄灭灯泡有的像。必须找到一个状态，再dfs。因为题目中说第1，n不能直接打。所以1，n只能通过打2，n-1消灭。然后从左到右打，消灭第i只有两种方式。
一：打第i只，需要打（hi+a-1）/a下。
二：打第i+1只，需要打（hi+b-1）/b下。
但是这里只考虑打打第i+1只，因为打第i-1只时，便是第一种打法。
开始考虑把第i只消灭，就消灭第i+1推导第n只。但是最后一只要特殊考虑。因为a>b;直接打本身更快，然后提交有几个样例WA了。

后来发现考虑有点问题，因为上面说因为打第i-1只时，便是第一种打法。因为打第i-1只时只打了（h(i-1)+b-1)/b）可能是小于（hi+a-1)/a的，这样打（h(i-1)+b-1)/b）~（hi+a-1)/a下第i-1只都会死亡，所以dfs打的次数。AC

#include<bits/stdc++.h>
using namespace std;

int s[20];
int min_s=0x7fffffff;
int n, a, b;

void dfs(int i, int ans)
{
    if(i==n)
    {
        min_s=min(min_s, ans);
        return;
    }
    if(s[i]<=0)
    {
        dfs(i+1, ans);
    }
    int m1=0;
    if(s[i]>0)//情况二
    {
        m1=(s[i]+b-1)/b;
        s[i]-=m1*b;
        s[i+1]-=m1*a;
        s[i+2]-=m1*b;
        dfs(i+1, ans+m1);
        s[i]+=m1*b;
        s[i+1]+=m1*a;
        s[i+2]+=m1*b;
    }
    int m2=(s[i+1]+a-1)/a;
    
    if(m2>m1) //（h(i-1)+b-1)/b小于（hi+a-1)/a
    {
        for(int j=m1+1;j<=m2;j++)
        {
            s[i]-=j*b;
            s[i+1]-=j*a;
            s[i+2]-=j*b;
            dfs(i+1, ans+j);
            s[i]+=j*b;
            s[i+1]+=j*a;
            s[i+2]+=j*b;
        }
    }

}

int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        s[i]++;
    }
    int m1=(s[1]+b-1)/b;//消灭第1只
    s[1]=0;
    s[2]-=a*m1;
    s[3]-=b*m1;

    int m2=(s[n]+b-1)/b;//消灭第n只
    m2=max(0, m2);
    s[n]=0;

    if(n-1>=0)
        s[n-1]-=a*m2;
    if(n-2>=0)
        s[n-2]-=b*m2;

    dfs(2, m1+m2);

    cout<<min_s<<endl;

    return 0;
}