https://ac.nowcoder.com/acm/contest/5803/B

题目描述

赛时提示：魔法值和财富值初始为0

帕秋莉掌握了一种金属性魔法
她决定去捡一些石头，施展点石成金魔法

帕秋莉将捡到的n块石头排成一排，并决定将一些石头点为黄金

对于第i块石头，如果将其变为黄金，会增加ai的财富，消耗bi的魔法（需要说明的是，就算魔法值不够，也可以操作，操作后魔法值归零）

否则，帕秋莉将会回复ci的魔法，但减少di的财富（财富值同理，可以无限制减少）

帕秋莉想知道，按照1-n的顺序以此操作每块石头，如何决策，可以使自己最后的收益值最大
只需要输出最大收益
收益值=财富值*魔法值

（提示：数值不会变为负数，即任何时候，如果数值小于了0，它会立即变为0）

输入描述:

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

输出描述:

一个整数表示答案

示例1

输入

2
1926 817 2003 627
1949 1001 1234 4321

输出

1952898

备注:

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

思路

因为n相对较小所以可以用dfs

import sys
n = int(input())
stone = []
for _ in range(n):
    s = list(map(int, sys.stdin.readline().strip().split()))
    stone.append(s)

def dfs(i, money, magic):
    if i == n:
        return money * magic

    res1 = dfs(i+1, money + stone[i][0], max(0, magic-stone[i][1]))
    res2 = dfs(i+1,  max(0, money-stone[i][3]), magic + stone[i][2])
    return max(res1, res2)

print(str(dfs(0, 0, 0)))