这题目真的把人雷了！
题目看上去是最简单的那种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;
}