题解：P10483 小猫爬山

Ice_rnfmabj · 2024-05-19 20:10:11 · 题解

猫猫不可以劈开！猫猫不可以劈开！！猫猫不可以劈开！！！

如果你看了讨论区，你会发现有一种做法，先加上所有猫的体重然后除以缆车的载重。但是很明显这样有时候猫就会被切开。

所以我想正解是 DFS，因为要求的是最少用几辆缆车，那么就先从大到小排个序，然后一只一只猫放到缆车里。当然，要最大化缆车的利用，那么就需要尽可能把猫塞进缆车里。

下面的代码里，我用 a_i 表示每只猫的体重，sum_i 代表第 i 号缆车现在的重量。如果 sum_i 加上 a_u 还小于等于载重的话，那就加上 a_u，然后进行下一层 DFS。当然 DFS 完之后还要还原回去。

但是以上是还能塞猫的情况，有时候猫太重了就只能再来一辆缆车了。所以出了循环，把 a_u 放进 sum_v 里，然后 DFS 下一层，开一个新的缆车并且用后面的猫。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101],ans,sum[101];
void dfs(int u,int v){
    if(v>=ans) return;
    if(u==n){
        ans=v;
        return;
    }
    for(int i=0;i<v;i++){
        if(sum[i]+a[u]<=m){
            sum[i]+=a[u];
            dfs(u+1,v);
            sum[i]-=a[u];
        }
    }
    sum[v]=a[u];
    dfs(u+1,v+1);
    sum[v]=0;
}
int main(){
    cin>>n>>m;
    ans=n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n,greater<int>());
    dfs(0,0);
    cout<<ans;
    return 0;
}