BZOJ 2667 cqoi2012 模拟工厂 贪心

题目大意:现在你有一个工厂,初始生产力为,每一时刻你可以进行如下操作: 1.将生产力提高1 2.生产一些产品,数量等于当前生产力的数值 现在你有的钱 求最大收益

跪shanest大爷。。。 由于,爆枚接受哪些订单 每次Check的时候,对于每段时间显然先提高生产力再生产产品 那么我可以考虑这一段内先尽量提高生产力 但是这样可能会导致生产力提高得太高而没有足够的时间生产产品使得某个订单失败 因此我们计算出对于后面的每一个订单,,最多花多少时间提高生产力可以满足如果用接下来的时间都生产的话不至于fail 由于产品数量是关于提高生产力次数的二次函数 因此解个方程就行了

;struct abcd{int tim,goods,money;friend istream& operator >> (istream &_,abcd &a){return scanf(“%d%d%d”,&a.tim,&a.goods,&a.money),_;}bool operator < (const abcd &a) const{return tim < a.tim ;}}a[M],stack[M];int n,top;long long ans;t,long long g){long long a=1,b=k-t,c=g-k*t;long long delta=b*b-4*a*c;if(delta<0)return -1;return (long long)(floor( (-b+sqrt(delta))/2/a +1e-7 )+1e-7);}bool Judge(){int i,j;long long productivity=1,_goods=0;for(i=1;i<=top;i++){long long sum=0;int _tim=stack[i].tim-stack[i-1].tim;for(j=i;j<=top;j++){sum+=stack[j].goods;if(sum>_goods)_tim=min(_tim, Calculate(productivity,stack[j].tim-stack[i-1].tim,sum-_goods) );}if(_tim<0)return false;productivity+=_tim;_goods+=productivity*(stack[i].tim-stack[i-1].tim-_tim);_goods-=stack[i].goods;}return true;}int main(){int i,j;cin>>n;for(i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);for(i=1;i<1<<n;i++){long long _money=0;top=0;for(j=1;j<=n;j++)if(i&(1<<j-1))stack[++top]=a[j],_money+=a[j].money;if( Judge() )ans=max(ans,_money);}cout<<ans<<endl;return 0;}

坚硬的城市里没有柔软的爱情,生活不是林黛玉,

BZOJ 2667 cqoi2012 模拟工厂 贪心

相关文章:

你感兴趣的文章:

标签云: