Description

有一个称为 “模拟工厂” 的游戏是这样的: 在时刻 \(0\), 工厂的生产力等于 \(1\). 在每个时刻, 你可以提高生产力或者生产商品. 如果选择提高生产力, 在下一个时刻时工厂的 生产力加 \(1\); 如果选择生产商品, 则下一个时刻你所拥有的商品数量增加 \(p\), 其中 \(p\) 是本时刻工厂的生产力.

有 \(n\) 个订单, 可以选择接受或者不接受. 第 \(i\) 个订单 \((t_i, g_i, m_i)\) 要求在时刻 \(t_i\) 给买家提供 \(g_i\) 个商品, 事成之后商品数量减少 \(g_i\), 而收入增加 \(m_i\) 元. 如果接受订单 \(i\), 则必须恰好在时刻 \(t_i\) 交易, 不能早也不能晚. 同一时刻可以接受 多个订单, 但每个订单只能被接受一次. 要求最后的总收入最大.

例如, 如果一共有两个订单 \((5, 1, 8)\) 和 \((7, 15, 3)\), 用如下策略是最优的: 时刻 \(0, 1, 2\) 提高生产力 (时刻 \(3\) 的生产力为 \(4\)) , 然后在时刻 \(3, 4\) 生产商品, 则在时刻 \(5\) 时将拥有 \(8\) 个商品. 此时接受第 \(1\) 个订单 (还会剩下 \(7\) 个商品), 并且在时刻 \(5, 6\) 继续生产商品, 则在时刻 \(7\) 时拥有 \(7 + 4 + 4 = 15\) 个商品, 正好 满足订单 \(2\).

Input

输入第一行包含一个整数 \(n\), 即订单数目. 以下 \(n\) 行每行三个整数 \(t_i, g_i, m_i\).

Output

输出仅一行, 为最大总收入. 输出保证在 32 位带符号整数范围内.

Sample Input

2
5 1 8
7 15 3

Sample Output

11

Data Range

对于 30% 的数据, 满足:\(n \leq 5, t_i \leq 100, g_i \leq 10^4, m_i \leq 10^4\)

对于 60% 的数据, 满足:\(n \leq 10, t_i \leq 100, g_i \leq 10^4, m_i \leq 10^4\)

对于 100% 的数据, 满足:\(n \leq 15, t_i \leq 10^6, g_i \leq 10^9, m_i \leq 10^9\)

Explanation

首先看到 \(n\) 这么小肯定就暴力枚举对不对......

枚举满足哪一些情况, 然后再逐步判断每种情况有没有可能可以实现.

判断这些情况就解一堆二元一次不等式就可以了 (然后选择可达到的生产力最大的位置), 并且保证这样能够满足手里的产品的数量均衡就可以了.

如果方程组解出来是负数或无解, 那么肯定到这个位置就被卡住了 (然后滚粗)

大概就是这个样子, 应该代码里都看得清 (就像所有其他的题解一样, 这个也对方程组一笔带过不给式子, 因为我实在是太弱了)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 20;

struct Consumer {
    lli time, goods, money;
} arr[maxn], vec[maxn];
bool operator < (Consumer a, Consumer b) {
    return a.time < b.time; }

int n, vec_cnt;

lli eval_prod_rate(lli prod, lli time, lli goods)
{
    lli a = 1, b = prod - time, c = goods - prod * time;
    lli delta = b * b - 4 * a * c;
    llf epsilon = 1e-7;
    // Impossible equation, must raise
    if (delta < 0)
        return -1;
    // Solve equation
    return (lli)(floor( (-b + sqrt(delta)) / (2 * a) + epsilon ) + epsilon);
}

bool judge_status(void)
{
    lli productivity = 1, // Current productivity rate
        goods = 0; // Current goods in possession
    for (int i = 1; i <= vec_cnt; i++) {
        // The goods required to produce
        lli req_goods = 0;
        // The rate of productivity needs to be increased / appended
        lli prod_time = vec[i].time - vec[i - 1].time;
        // Iterate for (n - i + 1) inequalities
        for (int j = i; j <= vec_cnt; j++) {
            req_goods += vec[j].goods;
            if (req_goods > goods)
                prod_time = min(prod_time, eval_prod_rate(
                    productivity,
                    vec[j].time - vec[i - 1].time,
                    req_goods - goods
                ));
        }
        // Unable to satisfy limitations
        if (prod_time < 0)
            return false;
        // Update productivity and goods
        productivity += prod_time;
        goods += productivity * (vec[i].time - vec[i - 1].time - prod_time) ;
        goods -= vec[i].goods;
    }
    return true;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld%lld", &arr[i].time, &arr[i].goods, &arr[i].money);
    sort(arr + 1, arr + 1 + n);
    // Done reading data. Checking every possibility on selecting which
    // consumer to satisfy his needs
    lli max_revenue = 0;
    for (int i = 1; i < (1 << n); i++) {
        lli cur_money = 0;
        // Adding available consumers to vector, for judging
        vec_cnt = 0;
        for (int j = 1; j <= n; j++)
            if (i & (1 << (j-1))) {
                vec[++vec_cnt] = arr[j];
                cur_money += arr[j].money;
            }
        // Judging, and if succeeded...
        if (judge_status())
            max_revenue = max(max_revenue, cur_money);
    }
    // Done judging and searching
    printf("%lld\n", max_revenue);
    return 0;
}