AcWing 165. 小猫爬山
原题链接
简单
作者:
GTDI
,
2022-12-11 19:58:44
,
所有人可见
,
阅读 129
三角
#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
int n, m;
int sum[N], cat[N];
int ans=N;
void dfs(int u, int k)// u表示现在已经枚举到第几只猫,k表示现在用到索道的数量
{
// 如果用到的索道的数量已经大于现在的最优解并且还没有枚举到最后一只猫,说明这种情况已经不符合题意
if(k>=ans) return;
// 如果枚举到了最后一只猫,更新答案,不用再比较, 因为上面的if语句已经比较了
if(u==n)
{
ans=k;
return;
}
for(int i=0;i<k;i++)
{
if(cat[u]+sum[i]<=m)
{
sum[i]+=cat[u];
dfs(u+1, k);
sum[i]-=cat[u];
}
}
sum[k]=cat[u];
dfs(u+1, k+1);
sum[k]=0;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>cat[i];
// 排序并且翻转,从大猫开始枚举,
// 因为大猫的选择性少,到后面的小猫的时候虽然体重小,但是由于前面的大猫已经选择了,留给小猫的机会少了,
//枚举的次数少了,比较省时间
sort(cat, cat+n);
reverse(cat, cat+n);
dfs(0, 0);
cout<<ans;
return 0;
}