原题链接
第一眼还以为是贪心，然后随便找了几组例子瞬间推翻贪心的想法。发现(nleqslant18)，显然是用爆搜+剪枝。
爆搜主体我是对小猫进行枚举，判断增添缆车，其实这是一个比较慢的搜法，而另一个更快的搜法是通过枚举缆车，这样只要剪一点枝即可过，而我用的方法则需要更多剪枝才可过。
- 显然当搜索过程中若缆车的数量已经比之前的搜出的缆车数量多，即可直接返回，因为当前不可能比之前的更优。
- 枚举小猫时，为了可以不用枚举已经登上缆车的小猫，可以使用双向链表来储存小猫，递归前将这次枚举的小猫(O(1))删除，回溯时再接回上去即可。
- 输入时算出小猫总重，然后在搜索时记录还没登上缆车的小猫的总重，若剩余总重可以塞到一个缆车里，就直接判断并返回。
- 用剩余总重除以缆车能承载的最大重量(上取整)，显然后面需要的缆车不可能优于这个数，因此直接和记录的最少需要缆车数比较，若超过即可直接返回。
- 开一个数组，使用压位的方式记录某个决策下需要的最小缆车数，因为(nleqslant18)，所以可以开得下。
上述剪枝中(1,4,5)是重要的剪枝，缩短搜索时间主要靠这几个。
另外，我建议搜索时枚举缆车更好，这样剪枝少，且代码简单，不用想我打的这么麻烦。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 20;
struct dd {
int pre, suc, wht;
};
dd a[N];
int v[300000], n, w, s = 1e9, mi;
int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c<'0' || c>'9'; c = getchar())
p = (c == '-' || p) ? 1 : 0;
for (; c >= '0'&&c <= '9'; c = getchar())
x = x * 10 + (c - '0');
return p ? -x : x;
}
int comp(dd x, dd y)
{
return x.wht > y.wht;
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
void de(int x)
{
a[a[x].pre].suc = a[x].suc;
a[a[x].suc].pre = a[x].pre;
}
void con(int x)
{
a[a[x].pre].suc = x;
a[a[x].suc].pre = x;
}
void dfs(int nw, int k, int t, int tw, int sol)
{
int i = a[n + 1].pre;
if (s == mi)
return;
if (k >= s)
return;
if (ceil(tw / w) + k >= s)
return;
if (tw <= w)
{
s = minn(s, nw + tw <= w ? k : k + 1);
return;
}
if (t == n)
{
s = minn(s, k);
return;
}
if (nw + a[i].wht > w)
{
nw = 0;
k++;
}
if (k >= s)
return;
for (i = a[0].suc; i<=n; i = a[i].suc)
if (k < v[sol | (1 << (i - 1))] && nw + a[i].wht <= w)
{
de(i);
v[sol | (1 << (i - 1))] = k;
dfs(nw + a[i].wht, k, t + 1, tw - a[i].wht, sol | (1 << (i - 1)));
con(i);
}
}
int main()
{
int i, o = 0;
n = re();
w = re();
for (i = 1; i <= n; i++)
a[i].wht = re();
sort(a + 1, a + n + 1, comp);
for (i = 1, a[0].suc = 1, a[n + 1].pre = n; i <= n; i++)
{
o += a[i].wht;
a[i].pre = i - 1;
a[i].suc = i + 1;
}
memset(v, 60, sizeof(v));
de(1);
mi = ceil(o / w);
v[1] = 1;
dfs(a[1].wht, 1, 1, o - a[1].wht, 1 << (n - 1));
printf("%d", s);
return 0;
}