這題目真的把人雷了！
題目看上去是最簡單的那種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;
}