题解 | #「金」点石成金#

修补骑士原本想修补一下自己的DFS，却发现这道题并非传统板子的DFS，主要是没有回溯成分

我们首先发现是一串石头“选不选”的问题，有点类似于传统的背包问题（好像是可以的？不过我没有写出来），我们看到n上限不大，就考虑直接暴搜。对于DFS或者这种递归的方法，我们一定要记住：只关注于当前干什么，怎么实现相应操作。

这道题就是对于每一块石头（也就是深度），我们可以选择“选择”或者“不选”，，之后两条分支路线分别拿到，之后比较出最大值return即可。对于究竟什么是“分支路线对应的值”，你管那么多干嘛，直接用DFS表示就可以了！

对于边界条件，那就是大家都知道的if(deep == n)，你返回magic * money就可以了，我们每一种选择的分支条件都会遇见属于自己的magic * money，之后向外走的时候我们会用max拿到最大的res，这样就会不断减少深度，也会不断的淘汰选择方式，到达最后就只会剩下一个

（对于最后究竟谁是谁，还是那句话，你在乎这么多干什么！）

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;

vector<int> a(17,0);
vector<int> b(17,0);
vector<int> c(17,0);
vector<int> d(17,0);
//只要确保大于，并且没有MLE问题就可以了

int dfs(int deep,int money,int magic)
{
    if(deep == n)
    {
        return money * magic;
    }
    else
    {   
        //我们在每一步的选或者不选怎么搞的来着。。。？
        
        int temp = magic - b[deep];
        
        if(temp < 0)
        {
            temp = 0;
        }
        
        int res = dfs(deep + 1,money + a[deep],temp);
        
        temp = money - d[deep];
        
        if(temp < 0)
        {
            temp = 0;
        }
        
        res = max(res,dfs(deep + 1,temp,magic + c[deep]));
        
        return res;   
    }
}

signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>n;
    
    for(int r = 0;r < n;r++)
    {
        cin>>a[r]>>b[r]>>c[r]>>d[r];
    }
    
    int res = dfs(0,0,0);
    
    cout<<res<<endl;
    
    return 0;
}