hello! 大家好！ 我叫许雍然 （用户名也叫许雍然，中文） // 有空去我自我介绍里看看，有喜报！！！ // “自我介绍”链接：自我介绍 我在下面会自己更新剪贴板，内容大部分是说说题目的部分 // 注：以下内容有任何问题请问老师，不要糊弄过去或者问我，我其实并不专业、标准
2026.7.19
今天说说 #P3052. [USACO12MAR] Cows in a Skyscraper G 这道题 链接是：#P3052. [USACO12MAR] Cows in a Skyscraper G 这道题还挺有意思的 首先，学过搜索的同学应该会想到用深搜去写，也就是枚举每个奶牛被放到了哪一组电梯里，代码大概是：
//暴力搜索
#include <bits/stdc++.h>
using namespace std;
int n, w;
int x[18 + 5];
int v[18 + 5];
int ans;
// 当前物品，已有分组组数
void dfs(int pos, int cnt)
{
if (pos == n + 1)
{
ans = min(ans, cnt);
return;
}
for (int i = 1; i <= cnt; i++)
{
if (v[i] + x[pos] <= w)
{
v[i] += x[pos];
dfs(pos + 1, cnt);
v[i] -= x[pos];
}
}
v[cnt + 1] = x[pos];
dfs(pos + 1, cnt + 1);
v[cnt + 1] = 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> x[i];
ans = n + 1;
dfs(1, 0);
cout << ans;
return 0;
}
//禁止抄袭！！！
// 不是我自己写的 // 禁止抄袭！！！ 但是提交上去后，只拿到了 32 分 那……该怎么优化呢？ 其实，非常简单！ 大家听过“剪枝”的代码操作吗？ 其实就是“去卡出题人”+“提前排除” 我们只需要做到“不如最优结果时就不看了”就行了，所以，给前面的代码再加上底下的部分：
// 部分代码
if (cnt>=ans) return;
// 禁止抄袭
// 禁止抄袭（上面） 即全部满分代码是：
// 剪枝代码
#include <bits/stdc++.h>
using namespace std;
int n, w;
int x[18 + 5];
int v[18 + 5];
int ans;
// 当前物品，已有分组组数
void dfs(int pos, int cnt)
{
if (cnt >= ans)
return;
if (pos == n + 1)
{
ans = min(ans, cnt);
return;
}
for (int i = 1; i <= cnt; i++)
{
if (v[i] + x[pos] <= w)
{
v[i] += x[pos];
dfs(pos + 1, cnt);
v[i] -= x[pos];
}
}
v[cnt + 1] = x[pos];
dfs(pos + 1, cnt + 1);
v[cnt + 1] = 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> x[i];
ans = n + 1;
dfs(1, 0);
cout << ans;
return 0;
}
//禁止抄袭！！！
// 不是我自己写的 // 禁止抄袭！！！ 至此，满分代码1 就算是完工了 当然，还有的同学想：那还可以用“状压 DP”来写吧！ 其实也是可以的，只不过有点太麻烦了 // “状压DP”我其实不太会，这里只把代码拿过来 其实，大概逻辑是这样的： “f[i][sta] 表示 i 组，选了 sta 这些物品，其中体积最小的那组的体积。 如果有了一个这样的合法的状态，就可以考虑塞一个新物品能否达成就要么放到最小的那组，要么新开一组。 新开一组的转移很好理解。如果放到最小的那组，显然就需要考虑每个物品放到“剩下所有物品中最小的那组”后的体积，这每个体积都是能达成的最小体积，这些最小体积中的最小值肯定就是最优的了。” // 直接把老师的拿过来了 大概代码是：
#include <bits/stdc++.h>
using namespace std;
int n, w;
int a[20];
int f[20][300000];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> a[i];
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= (1 << n) - 1; j++)
{
if (f[i][j] != 0x3f3f3f3f)
{
for (int k = 0; k <= n - 1; k++)
{
if (j & (1 << k))
continue;
if (f[i][j] + a[k + 1] <= w)
f[i][j + (1 << k)] = min(f[i][j + (1 << k)],
f[i][j] + a[k + 1]);
else
f[i + 1][j + (1 << k)] = min(f[i + 1][j + (1 << k)],
a[k + 1]);
}
}
}
}
for (int i = 0; i <= n; i++)
if (f[i][(1 << n) - 1] != 0x3f3f3f3f)
{
cout << i << endl;
break;
}
return 0;
}
// 禁止抄袭
// 不是我自己写的 // 禁止抄袭！！！ 这就是满分代码2了！ 总结一下：我自己更喜欢、更推荐“剪枝”的方法，代码也更好写一些 好了，今天就到这里了，送你一个小秘诀： 搜索+乱搞，NOIP 一等奖 // （虽然真实水平才达到NOI铜牌，但是夸张一点，也更押韵）