牛客算法周周练8 「金」点石成金 暴力

链接：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个物品,两种方案

• 方案1: 消耗魔法并获得金钱
• 方案2: 消耗金钱并获得魔法
• 每个物品必须执行其中一种方案

问如何执行方案可以得到最大的 $(魔法\ast 金钱)$(魔法∗金钱)

n很小,可以暴搜
枚举每一种情况,用二进制位来表示选哪种方案

#ifdef debug
#include <time.h>
// #include "/home/majiao/mb.h"
#endif
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
 
#define MAXN ((int)1e5+7)
#define ll long long
#define int long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)
 
using namespace std;
 
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
 
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
 
namespace FastIO{
 
   char print_f[105];
   void read() {}
   void print() { putchar('\n'); }
 
   template <typename T, typename... T2>
       inline void read(T &x, T2 &... oth) {
           x = 0;
           char ch = getchar();
           ll f = 1;
           while (!isdigit(ch)) {
               if (ch == '-') f *= -1;
               ch = getchar();
           }
           while (isdigit(ch)) {
               x = x * 10 + ch - 48;
               ch = getchar();
           }
           x *= f;
           read(oth...);
       }
   template <typename T, typename... T2>
       inline void print(T x, T2... oth) {
           ll p3=-1;
           if(x<0) putchar('-'), x=-x;
           do{
                print_f[++p3] = x%10 + 48;
           } while(x/=10);
           while(p3>=0) putchar(print_f[p3--]);
           putchar(' ');
           print(oth...);
       }
} // namespace FastIO
using FastIO::print;
using FastIO::read;
 
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int n, m, K;
 
signed main() {
#ifdef debug
    freopen("test.txt", "r", stdin);
    clock_t stime = clock();
#endif
    read(n);
    for(int i=1; i<=n; i++)
        read(a[i], b[i], c[i], d[i]);
    int N = 1 << n, ans = 0;
    for(int i=0; i<N; i++) {
    	/** sum获得的金钱, mf当前魔法 */
        int tmp = i, k = 1/**当前物品*/, sum = 0, mf = 0;
        while(k <= n) { //
            if(tmp & 1) { //第一种方案
                sum += a[k];
                mf -= b[k];
            } else { //第二种方案
                sum -= d[k];
                mf += c[k];
            }
            sum = max(sum, 0ll); //题目中说负数会立马变成0
            mf = max(mf, 0ll);
            k ++;
            tmp >>= 1;
        }
        ans = max(ans, mf*sum);
    }
    printf("%lld\n", ans);
 
 
#ifdef debug
   clock_t etime = clock();
// printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
   return 0;
}