数量不多的几道dfs独立完成的题目啊，写一个题解留个纪念

题目描述

小Q打算穿越怪兽谷，他不会打怪，但是他有钱。

他知道，只要给怪兽一定的金币，怪兽就会一直护送着他出谷。

在谷中，他会依次遇见N只怪兽，每只怪兽都有自己的武力值和要“贿赂”它所需的金币数。

如果小Q没有“贿赂”某只怪兽，而这只怪兽“武力值”又大于护送他的怪兽武力之和，这只怪兽就会攻击他。

小Q想知道，要想成功穿越怪兽谷而不被攻击，他最少要准备多少金币。

输入格式
第一行包含整数N，表示怪兽的数量。

第二行包含N个整数d1,d2,…,dn，表示每只怪兽的武力值。

第三行包含N个整数p1,p2,…,pn，表示收买N只怪兽所需的金币数。

输出格式
输出一个整数，表示所需最小金币数。

数据范围
1≤N≤50,
1≤di≤1012,
1≤pi≤2
输入样例1：
3
8 5 10
1 1 2
输出样例1：
2
输入样例2：
4
1 2 4 8
1 2 1 2
输出样例2：
6

样例

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int p[N];
typedef long long ll;
ll d[N];
int n;
int ans=INT_MAX;
bool vis[N];
void dfs(int cnt,ll health,int pay)
{
    if(pay>=ans)return;
    if(cnt>=n)
    {
        ans=min(ans,pay);
        return;
    }


     if(!vis[cnt])
     {
         vis[cnt]=true;
         dfs(cnt+1,health+d[cnt],pay+p[cnt]);
         vis[cnt]=false;
     }
     if(health>=d[cnt])
     dfs(cnt+1,health,pay);

}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>d[i];
    for(int i=0;i<n;i++)cin>>p[i];
    dfs(0,0,0);
    cout<<ans;
    return 0;

}

算法1

(dfs) $O(n^2)$

本题加了一些剪枝操作，玄学时间复杂度吧
这个题第一眼看到写成了二分，但是后来发现想假了，又看了一眼如此小的数据，想起了y总说过的数据比较小话，一般就是爆搜，哎dfs，一开始没加剪枝tle了

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla