[CQOI2012]模拟工厂 题解(搜索+贪心)

题解
阅读体验：https://zybuluo.com/Junlier/note/1327574

链接题目地址：洛谷P3161 BZOJ P2667
这个题练一练综合思想还是不错的。。。（然而蒟蒻不会啊）

做法

肯定是在能完成某些订单的情况下使自己生产力越高越好是吧（一个大致的贪心方向）
但是我们不知道自己到底应该怎么去决定提高生产力时间
那么换个角度，不从时间来看，从订单上来看

贪心

我们假设一定要完成订单$1～n$
那么应该如何贪心选时间提升生产力呢，当然是在能满足所有订单的基础上尽量多地提高生产力
那么对于订单$i$和$j$，我们都会得到方程：(设$pdc(produce)$为完成订单$i$时的生产力，$T$为距离$j$订单的时间，$x$为用来提升生产力的时间，$gv(give)$是订单$j$需求量)

$$(pdc+x)×(T-x)=gv$$ 对所有我们一定要完成的订单一个一个完成，每次完成一个订单时对它之后的每一个订单我们都解这么一个方程，得到尽可能的休息时间，那么这样子一定是对的吧

然后可以想到

上面是$1～n$我们都想完成，现在不同了，我们可以放弃一些订单
再看数据范围：$n<=15$？，那不就暴力枚举状态选还是不选啊
然后对于上面那个方程，如果无解$△ < 0$肯定这种计划是不行的
然后直接用求根公式会得到：

$$\frac{T-pdc+\sqrt{(pdc+T)^2-4×gv}}{2}$$ 算一下时间复杂度：$O(2^n×n^2)$很对呀，那就做完了
枚举状态虽可以直接枚举，但也可以搜是吧，那我们就叫他搜索了

给出代码

哼哼～压行是看代码人的噩梦，是写代码者的美梦（虽然笔者只稍稍压行了。。。）

#include<bits/stdc++.h>
#define il inline
#define rg register
#define ldb double
#define lst long long
#define rgt register int
#define N 20
#define M 100050
using namespace std;
const int Inf=1e9;
il lst MAX(rg lst x,rg lst y){return x>y?x:y;}
il lst MIN(rg lst x,rg lst y){return x<y?x:y;}
il int read()
{
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
int n,UP;
lst Ans,Res;
int sgn[N],top;
struct DD{lst tt,gv,gt;}ljl[N];
bool cmp(const int&a,const int&b){return ljl[a].tt<ljl[b].tt;}
il void Solve(rgt Zt)
{
    top=Res=0;
    for(rgt i=1;i<=n;++i)
        if(Zt&(1<<(i-1)))sgn[++top]=i,Res+=ljl[i].gt;
    if(Res<Ans)return;
    sort(&sgn[1],&sgn[top+1],cmp);
    rg lst pdc=1,rest=0;
    rg bool flag=true;
    for(rgt i=0;i<top;++i)
    {
        rg lst nd=0,brk=Inf;
        for(rgt j=i+1;j<=top;++j)
        {
            nd+=ljl[sgn[j]].gv;
            rg lst tm=ljl[sgn[j]].tt-ljl[sgn[i]].tt;
            rg lst b=pdc-tm,c=nd-rest-pdc*tm;
            if(b*b-4*c<0){flag=false;break;}//delta
            rg lst x=(sqrt(b*b-4*c)-b)/2;
            brk=MIN(brk,x);
        }pdc+=brk;
        rest+=pdc*(ljl[sgn[i+1]].tt-ljl[sgn[i]].tt-brk)-ljl[sgn[i+1]].gv;
        if(!flag||brk<0||rest<0){flag=false;break;}
    }if(flag)Ans=MAX(Ans,Res);
}
int main()
{
    n=read(),UP=(1<<n);
    for(rgt i=1;i<=n;++i)
        ljl[i]=(DD){read(),read(),read()};
    for(rgt i=1;i<UP;++i)Solve(i);
    return printf("%lld\n",Ans),0;
}