[CQOI2012]模拟工厂

NC19923. [CQOI2012]模拟工厂

描述

有一个称为“模拟工厂”的游戏是这样的：在时刻0，工厂的生产力等于1。在每个时刻，你可以提高生产力或者生产商品。如果选择提高生产力，在下一个时刻时工厂的生产力加1；如果选择生产商品，则下一个时刻你所拥有的商品数量增加p，其中p是本时刻工厂的生产力。有n个订单，可以选择接受或者不接受。第i个订单(t_i, g_i, m_i)要求在时刻t_i给买家提供g_i个商品，事成之后商品数量减少g_i，而收入增加m_i元。如果接受订单i，则必须恰好在时刻ti交易，不能早也不能晚。同一时刻可以接受多个订单，但每个订单只能被接受一次。要求最后的总收入最大。

例如，如果一共有两个订单(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。

输入描述

输入第一行包含一个整数n，即订单数目。
以下n行每行三个整数t_i, g_i, m_i。

输出描述

输出仅一行，为最大总收入。输出保证在32位带符号整数范围内。

示例1

输入:

2
5 1 8
7 15 3

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 488K, 提交时间: 2020-03-29 00:04:20

#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[20];
int q[20],tot;
ll gets(ll a,ll b,ll c)
{
	ll de=b*b-4*a*c;
	if(de<0) return -1;
	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=0;
void solve(int x)
{
	ll sum=0,tot=0;
	for(int i=1;i<=n;i++)
	if((1<<(i-1))&x) q[++tot]=i;
	ll s=0,g=1;
	for(int i=1;i<=tot;i++)
	{
		ll tmp=2147483647ll,now=0;
		for(int j=i;j<=tot;j++)
		{
			now+=t[q[j]].g;
			ll b=t[q[j]].tim-t[q[i-1]].tim;
			tmp=min(tmp,gets(-1,b-g,b*g+s-now));
			if(tmp<0)
			{
				sum=0;
				return;
			}
		}
		g+=tmp;
		s+=g*(t[q[i]].tim-t[q[i-1]].tim-tmp);
		sum+=t[q[i]].m;
		s-=t[q[i]].g;
	}
	ans=max(ans,sum);
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	scanf("%lld%lld%lld",&t[i].tim,&t[i].g,&t[i].m);
	sort(t+1,t+n+1);
	for(int i=0;i<=(1<<n)-1;i++) solve(i);
	printf("%lld",ans);
}