51Nod 蜥蜴和地下室（搜索）

哈利喜欢玩角色扮演的电脑游戏《蜥蜴和地下室》。此时，他正在扮演一个魔术师。在最后一关，他必须和一排的弓箭手战斗。他唯一能消灭他们的办法是一个火球咒语。如果哈利用他的火球咒语攻击第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
端点变为0是已知的，中间搜索时就是每次确定当前搜索的点的前一个点生命值为负数

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <stack>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <cassert>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#pragma comment(linker, "/stck:1024000000,1024000000")

#define lowbit(x) (x&(-x))

#define max(x,y) (x>=y?x:y)

#define min(x,y) (x<=y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.1415926535897932384626433832

#define ios() ios::sync_with_stdio(true)

#define INF 0x3f3f3f3f

#define mem(a) ((a,0,sizeof(a)))

typedef long long ll;

int n,a,b,h[],ans=,pos=,cnt=INF;

void dfs(int now,int value)

{

    if(now==n)

    {

        cnt=min(cnt,value);

        return ;

    }

    int x=,y=;

    if(h[now-]<) dfs(now+,value);

    else

    {

        x=h[now-]/b+;

        h[now-]-=b*x;h[now]-=a*x;h[now+]-=b*x;

        dfs(now+,value+x);

        h[now-]+=b*x;h[now]+=a*x;h[now+]+=b*x;

    }

    y=h[now]/a+;

    if(h[now]>= && y>x)

    {

        for(int i=x+;i<=y;i++)

        {

            h[now-]-=b*i;h[now]-=a*i;h[now+]-=b*i;

            dfs(now+,value+i);

            h[now-]+=b*i;h[now]+=a*i;h[now+]+=b*i;

        }

    }

}

int main()

{

    scanf("%d%d%d",&n,&a,&b);

    for(int i=;i<=n;i++)

        scanf("%d",&h[i]);

    ans=h[]/b+;

    h[]-=b*ans;

    h[]-=a*ans;

    h[]-=b*ans;

    if(h[n]>=)

    {

        pos=h[n]/b+;

        h[n]-=b*pos;

        h[n-]-=a*pos;

        h[n-]-=b*pos;

    }

    dfs(,);

    if(cnt==INF) printf("%d\n",ans+pos);

    else printf("%d\n",ans+pos+cnt);

    return ;

}