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

#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;
}