- 题面
- 题目思路：这是一道模拟赛压轴题，当时我天真的认为这是一道简单的01背包题，但一看数据范围，顿时懵逼，就算用map代替数组，但也会TLE。一般的背包题的物品数量和物品价值都是适量的，而本题物品数量不多，但物品价值远远超出了普通的限度。本题的正解是爆搜，高大上一点叫折半搜索，英文名Meet In The Middle，即二分搜索，枚举方案数，最后将两边的方案数进行匹配。本题还有一些优化，类似于dfs中进行归并排序，优化常数，但这些我不会。。。
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
int sc() {
int xx = 0, ff = 1; char cch = gc;
while (cch < '0' || cch > '9') {
if (cch == '-') ff = -1; cch = gc;
}
while (cch >= '0'&& cch <= '9') {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
int n, m;
ll len1, len2, now;
ll a[Maxm<<1], b[Maxm<<1];
int v[Maxn];
void dfs1(int nowl,int nowr, int sum) {
if(nowl == nowr) {
a[++len1] = sum;
if(sum + v[nowl] <=m)
a[++len1] = sum + v[nowl];
return ;
}
dfs1(nowl + 1, nowr, sum); //两种选择，选 或 不选
if(sum + v[nowl] <= m)
dfs1(nowl + 1, nowr, sum + v[nowl]);
}
void dfs2(int nowl,int nowr, int sum) {
if(nowl == nowr) {
b[++len2] = sum;
if(sum + v[nowl] <=m)
b[++len2] = sum + v[nowl];
return ;
}
dfs2(nowl + 1, nowr, sum);
if(sum + v[nowl] <= m)
dfs2(nowl + 1, nowr, sum + v[nowl]);
}
int main() {
n = sc(); m = sc();
for(int i = 1; i <= n; i++)
v[i] = sc();
int L = n >> 1;
dfs1(1, L, 0); //折半搜索
dfs2(L + 1, n, 0);
sort(a + 1, a + len1 + 1);
sort(b + 1, b + len2 + 1);
int l = 1, r = len2; //进行匹配，伪指针优化
while(l <= len1) { //因为序列是有序的，所以我们可以用一个变量当做指针，每次匹配时直接从上一个匹配完的位置开始即可
while(l <= len1 && a[l] + b[r] <= m) { //可以优化时间
if(now < a[l] + b[r])
now = a[l] + b[r];
l++;
}
r--;
}
printf("%lld\n", now);
return 0;
}