poj3628 Bookshelf2

/*** 题目：书架2 题意： 农夫约翰最近给奶牛图书馆买了一个新的书架，但是书架很快就要被填满了。 现在只有最上面的那一层有空位。 约翰有N(1 <= N <= 20)只高度为Hi(1 <= Hi <= 1,000,000 - 这是 些很高的奶牛)的奶牛。书架高度为B(1 <= B <= S，S是所有奶牛高度之和)。 为了能碰到书架的最顶层，一个或更多的奶牛会相互堆叠形成一个栈，因此栈 的总高度会是这些奶牛的高度之和。为了能够碰到书架的最顶层，总高度必须不低 于书架的高度。 因为一个太高的奶牛栈会有危险，你的工作是找到一个奶牛的集合，这个集合形 成的栈的高度最小且能碰到书架的最顶层。你的程序应该输出最优的奶牛栈高度和 书架高度的差值。 思路：状态数最多2^20，直接暴力递推就行了。。。 ***/ #include<stdio.h> #include<string.h> const int MAXS = 1 << 20; int H[MAXS + 10]; int main() { int N, B, ans; scanf("%d%d", &N, &B); for(int i = 0; i < N; i++) { scanf("%d", &H[1 << i]); } for(int i = 0; i < (1 << N); i++) { if(H[i] >= B) { if(ans > H[i] - B) ans = H[i] - B; continue; } for(int j = 0; j < N; j++) { if(!(i & (1 << j))) H[i|(1 << j)] = H[i] + H[1 << j]; } } printf("%d\n", ans); return 0; }