题解 P3161 【[CQOI2012]模拟工厂】

CYJian · 2018-04-05 15:03:58 · 题解

震惊！一道爆搜题竟然被评成了黑题！！！

咳咳。。。

没错，这道题就是一道爆搜题。。。

n <= 15，这让我们习惯性的想到了状压。。。

然后仔细想想，如果我们已经选好了要接受哪些订单，可不可以直接判断呢？？

或者说更进一步，如果已经知道当前的生产力、剩了多少东西、接下来还有哪些订单，我们能不能求出在接下一个订单之前可以有多少时间提高生产力呢？？

（这么多废话终于说完了。。。）

说了这么多显然是可以的嘛。。。

我们设可以有x单位时间来提高生产力，那么如果当前离下一个订单的时间为T时，这个订单要P个产品，工厂拥有M的生产力时，显然有如下方程：

整理后就可以得到：

利用根的判别式算一下有没有根，如果没有就说明无法接下这个订单，否则就可以拥有

的时间来增加生产力。

然后就这样枚举下去，每次如果方案可行就用这些订单的收入来更新答案。

下面贴代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 20;

struct P {
    int t; //订单的时间
    int c; //需要的产品数量
    int p; //得到的报酬

    friend bool operator< (P a, P b) { //按照时间排好序
        return a.t < b.t;
    }
}S[N], a[N];

int n;
int tot;
ll res;
// 设可以有x天提高生产力则可以列出方程: (Make + x) * (Time - x) = Need
// 整理得: x^2 + (Make - Time) * x + Need - Make * Time = 0
// 解方程即可
ll js(ll Make, ll Time, ll Need) { 
    ll a = 1;
    ll b = Make - Time;
    ll c = Need - Make * Time;
    ll derta = b * b - 4 * a * c;
    if(derta < 0) return -1;
    return floor((-b + sqrt(derta)) / 2 / a);
}
//检查当前枚举的方案可不可行，可行就更新答案
void solve(int Now) {
    tot = 0;
    ll num = 0;
    for(int i = 1; i <= n; i++)
        if(Now & (1 << i - 1))
            S[++tot] = a[i], num += a[i].p; //将当前状态的订单加入栈
    ll Make = 1; //生产力
    ll Have = 0; //剩余的产品数量
    for(int i = 1; i <= tot; i++) {
        ll t = S[i].t - S[i - 1].t; //在下一个订单前能够提高生产力的时间，最大就是这个
        ll sum = 0; //累加所需的产品
        for(int j = i; j <= tot; j++) {
            sum += S[j].c;
            if(sum > Have)
                t = min(t, js(Make, S[j].t - S[i - 1].t, sum - Have)); //用算出来的时间更新当前的时间
        }
        if(t < 0) return ; //说明不可行
        Make += t; //更新生产力
        Have += Make * (S[i].t - S[i - 1].t - t) - S[i].c; //更新库存
    }
    res = max(res, num);
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d%d", &a[i].t, &a[i].c, &a[i].p);
    sort(a + 1, a + 1 + n); //按照时间排好序
    for(int i = 0; i < (1 << n); i++)
        solve(i);
    printf("%lld\n", res);
    return 0;
}