這題目真的把人雷了！
題目看上去是最簡單的那種01背包，但范圍是 2^30 特別大，所以必然就不能用背包來做，只能搜索。
題目說 N <= 1000，還說輸入的數據中，一個數大于它前面兩個數的和。
所以就一直在想，是不是能利用這種特性來做些什么，但是思考了很久，無果。
看到題目 1400 / 300 的通過率，就認定這是一道難題了，基本做不出來了。
于是就直接看了下數據，發現 N 最大才 40 ！
寫了一個很簡單的搜索，0ms 就過了。被瞬間雷倒了！
為什么這道題要這樣整蠱人呢？
看到 Discuss 里面有人提到“斐波那契數列”。忽然發現，題目的數據不就是跟“斐波那契”差不多嗎！
只不過增長的還要快一點。
寫了個程序測了下，發現第 46 項的和就已經超過 2^30 了。瞬間又無語了。
所以這題目確實是一道牛題！

#include <stdio.h>
#include <math.h>

int detect_range()
{
    double f, n;

    for (n = 1; n < 100; n++) {
        f = pow(((sqrt(5.0) + 1) / 2), n);
        printf("%d -> %lf\n", (int)n, f);
        if ((int)f > (1 << 30))
            break;
    }

    return 0;
}

#define MAX_N 64

__int64 sum[MAX_N], data[MAX_N], min_val, C;
int N;

void dfs(int idx)
{
    while (idx > 0 && data[idx] > C) 
        idx--;
    while (idx > 0 && sum[idx] >= C) {
        C -= data[idx];
        dfs(idx - 1);
        C += data[idx];
        dfs(idx - 1);
        idx--;
    }
    if (C - sum[idx] < min_val)
        min_val = C - sum[idx];
}

int main()
{
    int i;

    freopen("e:\\test\\in.txt", "r", stdin);

    scanf("%d%I64d", &N, &C);
    for (i = 1; i <= N; i++) {
        scanf("%I64d", &data[i]);
        sum[i] = sum[i - 1] + data[i];
    }
    min_val = C;
    while (data[N] > C)
        N--;
    dfs(N);
    printf("%I64d\n", C - min_val);

    return 0;
}