【搜索】【Meet in the middle】世界冰球锦标赛Ice Hockey World Championship

时间： 2023-07-09 admin 互联网

题目描述

译自 CEOI2015 Day2 T1「Ice Hockey World Championship」

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入

第一行，两个正整数 N 和 M(1≤N≤40,1≤M≤10^18)，表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行，N 个以空格分隔的正整数，均不超过 10^16，代表每场比赛门票的价格。

输出

输出一行，表示方案的个数。由于 N 十分大，注意：答案 ≤240。

输入样例

5 1000
100 1500 500 500 1000

输出样例

说明

样例解释

八种方案分别是：

一场都不看，溜了溜了
价格 100 的比赛
第一场价格 500 的比赛
第二场价格 500 的比赛
价格 100 的比赛和第一场价格 500 的比赛
价格 100 的比赛和第二场价格 500 的比赛
两场价格 500 的比赛
价格 1000 的比赛

有十组数据，每通过一组数据你可以获得 10 分。各组数据的数据范围如下表所示：

数据组号	1-2	3-4	5-7	8-10
N≤	10	20	40	40
M≤	10^6	10^18	10^6	10^18

分析

首先考虑暴力解法。

枚举每场比赛的状态，算出所有方案，若方案满足条件计数器累加。

观察数据范围，这样做跑下来搜索树过于庞大。

考虑使用Meet in The Middle算法进行优化（参考博客 meet in the middle）

我们把所有的价格分成两部分，分别处理出方案，然后统计答案

代码

#include<bits/stdc++.h>
using namespace std;long long n, m;
long long p[47];
long long a[10000010], b[10000010];
long long cnta, cntb;
long long ans;inline long long read() {long long x = 0, f = 1; char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}return x * f;
}void dfs_a(long long l, long long r, long long sum) {if (sum > m) return;if (l > r) {a[++cnta] = sum;return;}dfs_a(l + 1, r, sum + p[l]);//选 dfs_a(l + 1, r, sum);//不选 
}void dfs_b(long long l, long long r, long long sum) {if (sum > m) return;if (l > r) {b[++cntb] = sum;return;}dfs_b(l + 1, r, sum + p[l]);//选 dfs_b(l + 1, r, sum);//不选 
}int main() {n = read(), m = read();for (long long i = 1; i <= n; i++) p[i] = read();dfs_a(1, n >> 1, 0);//分成两部分分别处理dfs_b((n >> 1) + 1, n, 0);sort(a + 1, a + cnta + 1);for (long long i = 1; i <= cntb; i++) ans += upper_bound(a + 1, a + cnta + 1, m - b[i]) - a - 1;//upper_bound(a + 1, a + cnta + 1, m - b[i])返回a数组中第一个大于等于m - b[i]的值的位置//因为a数组升序排序，所以upper_bound的返回值之前的所有值都满足条件printf("%lld", ans);
}

当然，各位大佬也可以将dfs数组写成带指针的形式，依照个人习惯而定