[BZOJ2667][cqoi2012]模拟工厂
试题描述
有一个称为“模拟工厂”的游戏是这样的：在时刻0，工厂的生产力等于1。在每个时刻，你可以提高生产力或者生产商品。如果选择提高生产力，在下一个时刻时工厂的生产力加1；如果选择生产商品，则下一个时刻你所拥有的商品数量增加 p，其中 p是本时刻工厂的生产力。
有 n个订单，可以选择接受或者不接受。第 i个订单( ti, gi, mi)要求在时刻 ti给买家提供 gi个商品，事成之后商品数量减少g i，而收入增加 mi元。如果接受订单 i，则必须恰好在时刻 ti交易，不能早也不能晚。同一时刻可以接受多个订单，但每个订单只能被接受一次。要求最后的总收入最大。
例如，如果一共有两个订单(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。
输入
输入第一行包含一个整数 n，即订单数目。以下 n行每行三个整数 ti, gi, mi。
输出
输出仅一行，为最大总收入。输出保证在32位带符号整数范围内。
输入示例
25 1 87 15 3
输出示例
11
数据规模及约定
n ≤ 15，ti ≤ 105，gi ≤ 109，mi ≤ 109
题解
发现 n 很小，我们可以 2n 枚举。然后检验答案时贪心。
首先明确，一段时间内如果提高生产力和生产的时间分别固定，那么一定是先提高生产力然后再生产最优。
如果当前有 p 的生产能力，并且已经处理完了前 i-1 个任务，那么我们可以算出对于第 i~n 个任务，算出当前时间到该任务还有多长时间（令这个时间长度为 Ti），算出第 i 到该任务总共需要生产多少产品（令这个产品数为 Gi），那么设 x 为提高生产力所用的时间可以列出不等式 (x + p)(Ti - x) ≥ Gi（就是一个开口向下的抛物线在一条水平直线的上方的部分），显然这样一个不等式的解集是一个区间 [li, ri]；那么现在有一个神奇的结论，取所有 ri 中最小的就是最优的方式，这个我也不知道怎么证。。。。。
#include#include #include #include #include #include #include using namespace std;int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define maxn 20#define oo 2147483647#define LL long longint n;struct Ord { int t; LL g, m; Ord() {} Ord(int _1, LL _2, LL _3): t(_1), g(_2), m(_3) {} bool operator < (const Ord& t) const { return this->t < t.t; }} os[maxn], get[maxn], gt[maxn];int getans(LL p, LL t, LL g) { LL A = -1, B = t - p, C = t * p - g; LL delta = B * B - 4.0 * A * C; if(delta < 0) return -1; double x = (-(double)B - sqrt((double)delta)) / (2.0 * A); return (int)x;}int main() { n = read(); for(int i = 0; i < n; i++) { int a = read(), b = read(), c = read(); os[i] = Ord(a, b, c); } sort(os, os + n); int all = (1 << n) - 1; LL ans = 0; for(int i = 0; i <= all; i++) { int cnt = 0, ct = 0; for(int j = 0; j < n; j++) if(i >> j & 1) get[++cnt] = os[j]; get[cnt+1].t = -1; for(int j = 1; j <= cnt; j++) if(get[j].t == get[j+1].t) get[j+1].g += get[j].g, get[j+1].m += get[j].m; else gt[++ct] = get[j]; gt[0].t = 0; int p = 1; LL pro = 0, sum = 0; for(int j = 1; j <= ct; j++) { int x = oo; LL G = 0; for(int k = j; k <= ct; k++) G += gt[k].g, x = min(x, getans(p, gt[k].t - gt[j-1].t, G - pro)); pro += ((LL)x + p) * (gt[j].t - gt[j-1].t - x) - gt[j].g; if(x < 0){ sum = -1; break; } sum += gt[j].m; p += x; }// printf("%lld\n", sum); ans = max(ans, sum); } printf("%lld\n", ans); return 0;}