题解：P10483 小猫爬山

2c_s · 2024-05-18 14:19:08 · 题解

题目传送门

思路

搜索即可。

读入数据后定义一组变量 sum，sum_i 表示第 i 个缆车的重量。枚举总共用几个缆车，搜索时传当前是第几个小猫上缆车和当前枚举到的总缆车数。每次搜索枚举这个小猫要进入的缆车，并进行有回溯的搜索。如果当前小猫重量 C_i+ 当前缆车总重 sum_p\le W，就将缆车总重加上小猫重，并继续枚举。

如果所有小猫都进入了缆车，说明此种情况下是最小总缆车数，输出并结束整个程序。

• 剪枝：搜索时只枚举到当前上车的小猫编号的缆车数，保证中间缆车没有空着的。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,w,a[N],sum[N];
void dfs(int p,int maxn){
//maxn 预定的总缆车数；p 当前小猫编号。
    if(p==n+1){
        cout<<maxn;
        exit(0);
    }
    for(int i=1;i<=maxn&&i<=p;++i){//i<=p 即为上文中的剪枝。
        if(sum[i]+a[p]<=w){
            sum[i]+=a[p];
            dfs(p+1,maxn);
            sum[i]-=a[p];
        }
    }
    return ;
}
signed main(){
    cin>>n>>w;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i){
        memset(sum,0,sizeof sum);//记得初始化。
        dfs(1,i);
    }
    return 0;
}

AC 记录