Description

一个工厂每一时刻可以提高 $1$ 生产力或者生产商品， $n$ 个订单给出时间，数量，收益，问最大收益。

$1\leqslant n\leqslant15$

Solution

首先 $2^n$ 枚举选哪个订单，然后判断是否可行。

从第一个订单开始，状态可以用剩余存量 $rem$ 和生产力 $pro$ 表示，如果当前是第 $i$ 个订单， $i-1$ 到 $i$ 之间时间为 $t$ ，那么枚举 $j$ 从 $i$ 到 $n$ ，对于 $i$ 到 $j$ 这一段都应该是满足总量的，对于 $j$ ，因为 $i\sim j-1$ 是已经满足了的，所以我们可以看成这些量都在 $j$ 的时刻，这样也不会影响对于总量是否合法的判断，这些量总量为 $sum$ ，若加生产力所需时间为 $x$ ，那么有 $(t-x)\times (pro+x)+rem\geqslant sum$ 即 $x^2+x\times(p-t)+s-r-t\times p\leqslant0$ ，可以解得 $x$ 的区间为 $[l_j,r_j]$ ，这时总量满足了，但无法判断之后生产的速度能否满足，因此要让 $pro$ 尽可能大，选最大的 $\lfloor r_j\rfloor$ 中的最小值即可。

Code

#include<bits/stdc++.h>

using namespace std;

int n;

#define MAXN 20

#define LL long long

#define INF 0x3f3f3f3f3f3f3f3f

struct query

{

	LL t,g,m;

}q[MAXN];

bool cmp(query a,query b){return a.t < b.t;}

bool sel[MAXN];

int s[MAXN],tot; 

long long ans = 0;

LL calc(LL t,LL pro,LL rem,LL sum)//x^2+x*(p-t)+s-r-t*p<=0 

{

	LL a = 1,b = pro - t,c = sum - rem - t * pro;

	LL delta = b * b - 4 * a * c;

	if(delta < 0)return -1;

	return (-b + sqrt((double)delta)) / 2;

}

void solve()

{

	tot = 0;

	for(int i = 1;i <= n;++i)if(sel[i])s[++tot] = i;

	LL pro = 1,rem = 0;

	for(int i = 1;i <= tot;++i)

	{

		LL sum = 0,t = q[s[i]].t - q[s[i - 1]].t;

		LL x = INF;

		for(int j = i;j <= tot;++j)

		{

			sum = sum + q[s[j]].g;

			x = min(x,calc(q[s[j]].t - q[s[i - 1]].t,pro,rem,sum));

		}

		if(x < 0)return;

		pro += x;

		rem = rem + (t - x) * pro - q[s[i]].g;

	}

	LL res = 0;

	for(int i = 1;i <= tot;++i)res += q[s[i]].m;

	ans = max(ans,res);

	return;

}

void dfs(int pos)

{

	if(pos == n + 1){solve();return;}

	sel[pos] = true;dfs(pos + 1);

	sel[pos] = false;dfs(pos + 1);

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lld%lld%lld",&q[i].t,&q[i].g,&q[i].m);

	sort(q + 1,q + 1 + n,cmp);

	dfs(1);

	cout << ans << endl;

	return 0;

}