2667: [cqoi2012]模拟工厂
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 367 Solved: 184
[Submit][Status][Discuss]
Description
有一个称为“模拟工厂”的游戏是这样的:在时刻0,工厂的生产力等于1。在每个时刻,你可以提高生产力或者生产商品。如果选择提高生产力,在下一个时刻时工厂的生产力加1;如果选择生产商品,则下一个时刻你所拥有的商品数量增加p,其中p是本时刻工厂的生产力。
有n个订单,可以选择接受或者不接受。第i个订单(t, g, m)要求在时刻t给买家提供g个商品,事成之后商品数量减少g,而收入增加m元。如果接受订单i,则必须恰好在时刻t交易,不能早也不能晚。同一时刻可以接受多个订单,但每个订单只能被接受一次。要求最后的总收入最大。
例如,如果一共有两个订单(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。
Input
输入第一行包含一个整数n,即订单数目。以下n行每行三个整数t, g, m。
Output
输出仅一行,为最大总收入。输出保证在32位带符号整数范围内。
Sample Input
2
5 1 8
7 15 3
5 1 8
7 15 3
Sample Output
11
HINT
编号 | 1-3 | 4-6 | 7-10 |
n | <=5 | <=10 | <=15 |
t | 100 | 100 | <=100,000 |
g | 10,000 | 10,000 | <=10 |
m | 10,000 | 10,000 | <=10 |
Source
考虑贪心,显然每一段先加生产力再生产。
枚举订单后n*n check。
check时我们设当前工作力为g,天数为t,现在剩余a
则得方程(g+x)(t-x)>=a+需求。可解出能够增加生产力的天数。
联立方程,可得若干个区间[l,r]。显然取最小的r作为增加生产力的天数。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
ll n;
struct data {
ll tim,g,m;
bool operator <(const data tmp)const {
return tim<tmp.tim;
}
}t[];
int q[],tot;
ll gets(ll a,ll b,ll c) {
ll de=b*b-*a*c;if(de<) return -;
double d=sqrt(de);
double x1=(-b-d)/(2.0*a),x2=(-b+d)/(2.0*a);
return max((ll)floor(x1),(ll)floor(x2));
}
ll ans=;
void solve(int x) {
ll sum=;tot=;
for(int i=;i<=n;i++) if((<<(i-))&x) q[++tot]=i;
ll s=,g=;
for(int i=;i<=tot;i++) {
ll tmp=2147483647ll,now=;
for(int j=i;j<=tot;j++) {
now+=t[q[j]].g;
ll b=t[q[j]].tim-t[q[i-]].tim;
tmp=min(tmp,gets(-,b-g,b*g+s-now));
if(tmp<) {sum=;return;}
}
g+=tmp;s+=g*(t[q[i]].tim-t[q[i-]].tim-tmp);sum+=t[q[i]].m;s-=t[q[i]].g;
}
ans=max(ans,sum);
}
int main() {
scanf("%lld",&n);
for(int i=;i<=n;i++) scanf("%lld%lld%lld",&t[i].tim,&t[i].g,&t[i].m);
sort(t+,t+n+);
for(int i=;i<=(<<n)-;i++) solve(i);
printf("%lld",ans);
}