「金」点石成金

链接：https://ac.nowcoder.com/acm/problem/53680

题目描述：

赛时提示：魔法值和财富值初始为0
帕秋莉掌握了一种金属性魔法 她决定去捡一些石头，施展点石成金魔法 帕秋莉将捡到的n块石头排成一排，并决定将一些石头点为黄金 对于第i块石头，如果将其变为黄金，会增加ai的财富，消耗bi的魔法（需要说明的是，就算魔法值不够，也可以操作，操作后魔法值归零） 否则，帕秋莉将会回复ci的魔法，但减少di的财富（财富值同理，可以无限制减少） 帕秋莉想知道，按照1-n的顺序以此操作每块石头，如何决策，可以使自己最后的收益值最大 只需要输出最大收益 收益值=财富值*魔法值 （提示：数值不会变为负数，即任何时候，如果数值小于了0，它会立即变为0）

输入描述：

第一行一个整数n
接下来n行，每行四个数，分别代表对应石头的a,b,c,d值

输出描述：

一个整数表示答案

数据范围：
对于20%的数据，1≤n≤2
对于100%的数据，1≤n≤15，0≤ai,bi,ci,di≤1,000,000

solution：

对于100%的n来说，n最多为15，因此此题可以用深搜来做
对于每次搜索严格意义上都有2种选择，最多运行 次
1.当魔法值大于等于需要消耗的魔法值时，选择消耗相应的魔法，否则只有清空魔法值才能增加财富值
2.当财富值大于等于恢复魔法所需的财富值，消耗相应财富值来恢复魔法值，否则只有财富值清零才能增加魔法值
3.递归结束条件是r==n
需要注意的是收益值可能非常大，所以要开long long

#include <bits/stdc++.h>
using namespace std;
int n,a[16],b[16],c[16],d[16];
long long sum=0;
void dfs(int r,long long mo,long long cai)
{
    if(r==n)
    {
        sum=max(sum,cai*mo);
        return;
    }
    if(mo>=b[r])
        dfs(r+1,mo-b[r],cai+a[r]);
    else
        dfs(r+1,0,cai+a[r]);
    if(cai>=d[r])
        dfs(r+1,mo+c[r],cai-d[r]);
    else
        dfs(r+1,mo+c[r],0);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    dfs(0,0,0);
    cout<<sum;
}