正在入侵艾泽拉斯的古尔丹偶然间得到了一颗邪能炸弹，经过研究，他发现这是一颗威力极其巨大且难以控制的炸弹。但是精通邪能的古尔丹突然有了一个大胆的想法，他对炸弹进行了一些小小的改造。这使得炸弹需要n天的充能才能爆炸，在这n天中，每天炸弹的邪能值都会产生波动，波动值为xi，古尔丹唯一能控制的是使邪能值增加xi或减少xi，如果邪能值小于0或大于MAX，那么炸弹将会损坏并失效。机智如古尔丹当然会做出最优选择。而作为反抗军的情报人员，你知道炸弹的初始邪能值为begin，寿命为n天以及每天的波动值xi。你需要知道在第n天炸弹可能达到的最大邪能值。

第一行为一个整数T，表示有T组测试实例。
对于测试实例：
第一行为三个整数 n，begin，MAX。1<=n<=50,0<=begin<=MAX,1<=MAX<=1000。
第二行一次为n个整数 x1,x2,x3,x4...xn。1<=xi<=1000

对于每组测试实例输出一行，表示第n天炸弹可能达到的最大邪能值，如果炸弹无法避免邪能值低于0或者高于MAX则输出-1。

2

3 5 10

5 3 7

3 3 8

5 2 10

10

-1

思路：当时的写的是dfs  ac了  可以构造一颗搜索树 然后搜索就好了
　　     题解是用的dp  设dp[i][j]为第i天时值为j的存在状态  1为存在  0为不存在  如果dp[i-1][j] = 1  那么可由此推出dp[i][j + Xi] 和 dp[i][j - Xi]的存在状态 
　　     若j在i-1和i阶段取值0～Max内都不存在的话 直接可以返回-1了
dfs:

#include <iostream>

#include <stdio.h>

#include <queue>

using namespace std;

int a[];

int n, b, Max;

int ans;

void dfs(int ret, int t)

{

    if (ret <  || ret > Max)

        return;

    if (t == n) {

        ans = max(ans, ret);

        return;

    }

    dfs(ret+a[t], t+);

    dfs(ret-a[t], t+);

}

int main()

{

    //freopen("1.txt", "r", stdin);

    int T;

    scanf("%d", &T);

    while (T--) {

        ans = -;

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

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

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

        dfs(b, );

        printf("%d\n", ans);

    }

    return ;

}

dp:

#include <iostream>

#include <stdio.h>

#include <cstring>

#include <algorithm>

using namespace std;

int dp[][];

int n, b, Max;

int x[];

int main()

{

    //freopen("1.txt", "r", stdin);

    int T;

    scanf("%d", &T);

    while (T--) {

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

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

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

        memset(dp, , sizeof(dp));

        dp[][b] = ;

        int flag;

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

            flag = ;

            for (int j = ; j <= Max; j++) {

                if (dp[i-][j]) {

                    if (j + x[i] <= Max) {

                        dp[i][j + x[i]] = ;

                        flag = ;

                    }

                    if (j - x[i] >= ) {

                        dp[i][j - x[i]] = ;

                        flag = ;

                    }

                }

            }

            if (flag == ) break;

        }

        int ans = -;

        for (int i = Max; i >= ; i--)

            if (dp[n][i]) {

                ans = i;

                break;

            }

        printf("%d\n", ans);

    }

    return ;

}