P3161[CQOI2012]模拟工厂题解。题目
其实发现这是一道状压，发现这道题是一道数学题，其实就很简单了。对于每一次的订单我们可以设：
- \(time\) 为距离下一个订单的时间。
- \(num\) 为这个订单要生产的数量。
- \(x\) 为生产能力。
- \(y\) 的时间可以用来提高工厂的生产力。那我们就可以得出公式：\((x+y)\times (time-y) = num\)
整理后：（一元二次方程应该都会对吧。）\(y^2+(x-time)\times y-x\times time+num\)
一个一元二次方程肯定要判根啊，如果有实数根那么就是有解。所以我们只需要对方程判根，有根那么这个订单就可以完成。
如果有实数根只需要解这个方程即可：\(\dfrac{time - x + \sqrt{(x-time)^2 - 4\times x\times time-4\times num}}{2 }\)
程序首先先枚举每一个状态：状压！毕竟 \(n\le15\)。然后就去计算每一个订单，进行计算，判断可行性，对可行的方案取 \(\max\) 即可。AC code：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
ll t,g,m;
}a[25],st[25];
ll n;
bool cmp(node a,node b){
return a.t < b.t;
}
ll jisuan(ll x,ll time,ll y){
ll a = 1;
ll b = x-time;
ll c = y-x*time;
ll delta = b*b-4*a*c;
if(delta>=0)return (ll)((-b+sqrt(delta)) / 2 / a);
return -1;
}
ll ans;
void run(ll zy){
ll t = 0;
ll sum =0;
for(int i = 1;i <= n;i++){
if(zy & (1<<(i-1))) {
st[++t] = a[i];
sum += a[i].m;
}
}
ll m=1;
ll sheng=0;
for(ll i = 1;i <= t;i++){
ll mt = st[i].t - st[i-1].t;
//最多提高生产力的时间
ll num=0;//所有产品累计
for(ll j =i;j<=t;j++){
num += st[j].g;
if(num > sheng){
mt = min(mt,jisuan(m,st[j].t-st[i-1].t,num-sheng));
}
}
if(mt == -1) return ;
m += mt;
sheng += m * (st[i].t-st[i-1].t-mt) - st[i].g;
}
ans = max(ans,sum);
}
int main(){
cin >> n;
for(ll i = 1;i <= n;i++){
cin >> a[i].t >> a[i].g >> a[i].m;
}
sort(a+1,a+1+n,cmp);
for(ll i = 0;i < (1<<n);i++){
run(i);//状压，2^n枚举所有订单可能性
}
cout << ans;
return 0;
}