[Acwing] 165.小猫爬山 记搜+剪支

前言

传送门 :

记忆化搜索 和 剪枝 也太美妙了吧

思路

我们可以通过 枚举小猫来做

对于一个小猫 我们可以

• 给它新开一个 缆车
• 考虑是否可以放到前面已经有的缆车上

因此我们直接按照这个思路,搜索就行了

CODE

#include 
using namespace std;
const int N = 20;
int cat[N],cap[N];

int n,w;
int ans = 0x3f3f3f3f;

bool cmp(int a,int b)
{
    return a>b;
}

///前i-1个猫,坐了cnt个车
void dfs(int now,int cnt)
{
    if(cnt >= ans)
        return ;

    if(now == n+1)
    {
        ans  = min(ans,cnt);
        return;
    }

    for(int i=1;in>>w;
    for(int i=1;i>cat[i];

    sort(cat+1,cat+1+n,cmp);

    dfs(1,0);
    cout