小猫爬山 | Wuhaoda's Blog

小猫爬山

传送门

http://contest-hunter.org:83/contest/0x20%E3%80%8C%E6%90%9C%E7%B4%A2%E3%80%8D%E4%BE%8B%E9%A2%98/2201%20%E5%B0%8F%E7%8C%AB%E7%88%AC%E5%B1%B1

反思

dfs大水题
第一眼看上去感觉是贪心
仔细思考一下发现贪心不对
加上数据规模很小 用搜索

然而简单的搜索错了很多次
比如在枚举第i个车厢能否装动cat时:

1
2
3
4
5
6
7
For(i, 1, now) {                  //还错过data[num]写成data[i]
if(cab[i] + data[num] < w) { //显然应该是 <=
cab[i] += data[num];
dfs(num + 1);
cab[i] -= data[num];
}
}

还有就是搜完n个cat后没有加return
然而这一题用到一些基本剪枝技巧
比如最优性剪枝 还有顺序剪枝(优先搜索重量大的cat)

AC代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define For(a, b, c) for(register int a = b; a <= c; ++a)
using namespace std;

int w, n, ans;
int data[20], now, cab[20];

void dfs(int num) {
if(now >= ans)
return;
if(num == n + 1) {
ans = now;
return;
}
For(i, 1, now) {
if(cab[i] + data[num] <= w) {
cab[i] += data[num];
dfs(num + 1);
cab[i] -= data[num];
}
}
++now;
cab[now] = data[num];
dfs(num + 1);
--now;
cab[now + 1] = 0;
}

int main() {
scanf("%d %d", &n, &w);
For(i, 1, n)
scanf("%d", &data[i]);
sort(data + 1, data + n + 1);
reverse(data + 1, data + n + 1);
ans = n;
dfs(1);
cout<<ans;
}