题目意思:
其实很简单啦就是给你n个高度,让你挑其中的几个摞起来。要求摞起来以后的总高度超过b,问你这样的高度的最小值是多少。
本题要点:
1、暴搜:
首先,n最大值是20, 很小,可以暴搜, 复杂度 O(2^20)
2、 dfs(int x, int sum)
x 表示当前处理到的下标(1 ~ x - 1 都处理完了)。
sum 表示 已经当前已经累加的高度。
每次 dfs, 可以选择这个身高 w[x], dfs(x + 1, sum + w[x]);
也可以不选择 dfs(x + 1, sum);
3、 剪枝:
当前的sum 加上后面所有的身高都不能达到 b 的话,return。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 22;
int w[MaxN], post[MaxN];
int n, height, ans = 0x3f3f3f3f;void dfs(int x, int sum)
{
if(sum >= height && ans >= (sum - height)) {
ans = sum - height;}if(x > n || sum + post[x] < height) //剪枝{
return;}dfs(x + 1, sum + w[x]);dfs(x + 1, sum);
}int main()
{
scanf("%d%d", &n, &height);for(int i = 1; i <= n; ++i){
scanf("%d", &w[i]);}for(int i = n; i >= 1; --i){
post[i] = post[i + 1] + w[i];}dfs(1, 0);printf("%d\n", ans);return 0;
}/* 5 16 3 1 3 5 6 *//* 1 */