[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;}//deltarg 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;
}
