A brief discussion on slope optimization

Profile

List the state transfer equation, if it can be reduced to the following form:

\[dp[i]=\min/\max(c[i]+d[j]+C) \]

At this time, we can use monotonic queue optimization to do\(O(n^2)\)arrive\(O(n)\)complexity.

Now consider a more general situation, if it is reduced to the following form:

\[dp[i]=\min/\max(a[i]\cdot b[j]+c[i]+d[j]+C) \]

At this time, monotonous queue optimization is no longer applicable, so it needs to be usedObligation optimization。

The idea of obligation optimization is to eliminate some decisions that cannot be become the optimal solution, so that the remaining decision points will form aConvex hull, then use monotonic queue, binary, balanced tree, CDQ division or Li Chao line segment tree to quickly transfer.

Theoretical explanation

There are two ways to understand slope optimization:

Algebraic method

Set up decision points\(j_2\)Better\(j_1\)。

There are: (\(<\)correspond\(\max\)，\(>\)correspond\(\min\)）

\[a[i]\cdot b[j_1]+c[i]+d[j_1]+C</>a[i]\cdot b[j_2]+c[i]+d[j_2]+C \]

Simplified:

\[a[i]\cdot b[j_1]+d[j_1]</>a[i]\cdot b[j_2]+d[j_2] \]

make\(Y(x)=d[x]\)，\(X(x)=b[x]\)，\(k=-a[i]\), let\(X(j_2)>X(j_1)\)。

Move the item to:

\[k</>\frac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)} \]

This means that the two decision points are represented by two points in a plane rectangular coordinate system, if the slope between the two points is less than (or greater than)\(k\), then the point behind is better than the point before.

Now we consider three points with the following positional relationship:

As shown in the picture,\(k_2<k_1\)。

Let's discuss below\(\max\)The situation.

when\(k<k_2<k_1\)When, then\(C\)Compare\(A\)excellent,\(B\)Compare\(C\)excellent,\(B\)Optimal.
when\(k_2\le k\le k_1\)When, then\(A\)、\(B\)At least one\(C\)excellent.
when\(k_2<k_1<k\)When, then\(A\)Compare\(C\)excellent,\(C\)Compare\(B\)excellent,\(A\)Optimal.

To sum up,In any case,\(C\)Nothing can be the best, can be deleted.

Promote the above nature for all decision-making points:

Delete all the decisions that cannot be the optimal decision.Lower convex hull：

Similarly, for\(\min\)The situation will form a convex bag.

Geometry

Let's discuss it first\(\max\)The situation:

\[dp[i]=\max(a[i]\cdot b[j]+c[i]+d[j]+C) \]

Remove\(\max\), and then move the item to:

\[-d[j]=a[i]\cdot b[j]+c[i]-dp[i]+C \]

We can\(-d[j]\)Think of as vertical coordinates,\(a[i]\)It is seen as a slope,\(b[j]\)As horizontal coordinates,\(c[i]-dp[i]+C\)Think of as a constant.

Then the state transfer equation can be transferred at this timeThink of as a form\(y=kx+b\)Straight line equation, where for the same\(i\)Slope\(k=a[i]\)It is the same.

To make\(dp[i]\)The maximum is to make the intercept of the equation\(b\)Try to be as small as possible.

Put all decision points\((b[j],-d[j])\)In a plane rectangular coordinate system:

The process of finding the best decision point can be regarded asTranslate a straight line with constant slope, the first point encountered from bottom to top must minimize the intercept., As shown in the figure:

In fact, this point is the point where the slope of the previous point is less than or equal to the current slope, and the slope of the subsequent point is greater than or equal to the current slope.

Now we consider changing the linear slope and find that the decision point that may be the optimal solution if and only if in the followingLower convex hullsuperior:

No matter how the slope is changed, it is impossible to be the smallest point from bottom to top.

Similarly, for\(\min\)The situation will form a convex bag.

I personally prefer geometry, which is more intuitive, so the following examples will use geometry to prove it.

Code implementation

For different situations, we have different ways to insert decision points and query the optimal solution (for details, you can see the following example):

Decision point horizontal coordinate (\(b[j]\)) Strictly increase, the slope of the straight line equation (\(a[i]\)) Strictly increase

Insert: You can maintain a queue storage decision -making point number\(j\), due to the horizontal coordinate of the decision point (\(b[j]\)) Strictly increase, and then strictly increase (or decrease) according to the nature of the convex hull slope,When inserting, the slope of the second element and the tail of the team is less than (or greater than) the tail of the team and the point to be inserted.。
Query: According to the optimal decision point and the slope of the previous point is less than (or greater than) equal to the current slope, and the slope of the next point is greater than (or less than) equal to the current slope, and then according to the slope of the straight line equation (\(a[i]\)) Strictly increase, so the horizontal coordinate of the optimal decision point is strictly increased, and there is no need to save the previous decision point, soAs long as the slope of the two elements of the team leader is less than (or greater than) the current slope, the team leader will be popped up until it cannot be popped up. The team leader is the best decision point.。
Complexity:\(O(n)\)。

Decision point horizontal coordinate (\(b[j]\)) Strictly increase, the slope of the straight line equation (\(a[i]\)) Not strictly increased

Insert: Due to the horizontal coordinate of the decision point (\(b[j]\)) Strictly increase and remain unchanged, the same as above.
Query: Due to the slope of the linear equation (\(a[i]\)) does not strictly increase, so the optimal decision point is no longer monotonic, and at this time, it can only be based on the monotonicity of the convex hull slopeTwo pointsFind the point where the slope of the previous point is less than (or greater than) is equal to the current slope, and the slope of the next point is greater than (or less than) is equal to the current slope.
Complexity:\(O(n\log n)\)。

Decision point horizontal coordinate (\(b[j]\)) Not strictly increased

Because the horizontal coordinates are not strictly increased, that is, the points that may be added between two points, the above method is not available.

It is possible to consider using dynamic maintenance of convex hulls or using CDQ separation and treatment offline methods, which will not be stated here.

Here is an excellent algorithm with low thinking content, small code volume and small constant:Li Chao Line Duanshu。

In fact, the tree of the Li Chao Line is not a dynamic convex bag, but to directly maintain the answer with its own characteristics.

Put some invariability:

\[dp[i]=c[i]+C+\min/\max(b[j]\cdot a[i]+d[j]) \]

we will\(\min/\max\)The equation in this is regarded as a linear equation\(y=kx+b\),in\(b[j]\)It's the slope,\(a[i]\)It is the horizontal coordinate at this time,\(d[j]\)It is the intercept.

Found that it's time toFind some straight lines\(y=b[j]\cdot x+d[j]\)exist\(x=a[i]\)The most value at, and this happens to be something maintained by Li Chao's line segment tree.

So, every time we just need to turn the line\(y=b[j]\cdot x+d[j]\)Insert Li Chaoshu and query all straight lines\(x=a[i]\)The most valuable update answer.

Time complexity:\(O(n\log n)\)。

example

P5785 [SDOI2012] Task Schedulelink

Description

There is on the machine\(n\)They form a sequence of tasks that need to be processed. These tasks are labeled\(1\)arrive\(n\)Therefore, the arrangement of the sequence is\(1 , 2 , 3 \cdots n\)Essence this\(n\)Each task is divided into several batches, each batch contains several adjacent tasks. From the moment\(0\)Initially, these tasks are processed in batches,\(i\)The time required to complete a task individually is\(T_i\)Essence The machine needs to start time before each batch of tasks begins\(s\), and the time required to complete this batch of tasks is the sum of the time required for each task.

Note that the same batch of tasks will be completed at the same timeEssence The cost of each task is its completion time multiplied by a cost factor\(C_i\)。

Please determine a packet solution to minimize the total cost.

Data range

\(T1:1\leq n \leq 5000,0\leq S\leq 50,1\leq T_i,C_i \leq 100\)

\(T2:1\leq n \leq 300000,0\leq S\leq 512,1\leq T_i,C_i \leq 100\)

\(T3:1\leq n \leq 300000,0\leq S\leq 512,0\leq C_i \leq 512,-512\leq T_i \leq 512\)

Problem solving

\(T1:\)

Naive DP, no optimization is required.

We are right\(c\)and\(t\)Make prefix and use prefix and replace the original array.

Status indicates:\(dp[i]\)Indicates before completion\(i\)The minimum cost of the task.
initialization:\(dp[0]=0\)。
Status transfer: Consider the last group assigned, set the last group to\(j+1\sim i\)First of all,\(dp[j]\)Add on the basis of\(t[i] \cdot (c[i] - c[j])\),but\(s\)It seems to be difficult to deal with, but found\(s\)It will have an impact on all subsequent tasks, so for the convenience of processing, we canTake it ahead of time to the total contribution to the subsequent\(s \cdot (c[n] - c[j])\)Directly count into the current range, therefore state transfer equation:

\[dp[i] = \min(dp[j] + t[i] \cdot (c[i] - c[j]) + s \cdot (c[n] - c[j])) \]
Answer:\(dp[n]\)。

Time complexity:\(O(n^2)\)。

\(T2：\)

because\(1\leq n \leq 300000\)，\(O(n^2)\)If it is not possible to pass, it is found that the state transfer equation meets the conditions for slope optimization, and consider slope optimization.

Simplify and move items:

\[dp[j] = (t[i]+s)\cdot c[j]+dp[i]-t[i]\cdot c[j]-s\cdot c[n] \]

To make\(dp[i]\)If smaller, then the intercept should be made as small as possible, so the decision point will form a lower convex hull.

because\(T_i,C_i \geq 1\), so prefix and strict addition, soHorizontal coordinate\(c[j]\)Strictly increase, intercept\(t[i]+s\)Strictly increase, just apply the first case.

\(T3：\)

at this time\(-512\leq T_i \leq 512\), so the intercept does not increase strictly and the others remain unchanged. Just find the decision point in two parts when querying.

Coding skills: To avoid errors when dealing with slopes,Can write a product form。

Code

\(T1：\)

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 5010;

int n, s;
ll t[N], f[N];
ll dp[N];

int main()
{
	ios :: sync_with_stdio(0);
	(0), (0);
	cin >> n >> s;
	for (int i = 1; i <= n; i++)
	{
		cin >> t[i] >> f[i];
		t[i] = t[i - 1] + t[i];
		f[i] = f[i - 1] + f[i];
	}
	memset(dp, 0x7f, sizeof dp);
	dp[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			dp[i] = min(dp[i], dp[j] + t[i] * (f[i] - f[j]) + s * (f[n] - f[j]));
		}
	}
	cout << dp[n] << endl;
	return 0;
}

\(T2：\)

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 3e5 + 10;

int n, s;
int t[N], c[N];
int dp[N], q[N];

int main()
{
	ios :: sync_with_stdio(0);
	(0), (0);
	cin >> n >> s;
	for (int i = 1; i <= n; i++)
	{
		cin >> t[i] >> c[i];
		t[i] += t[i - 1];
		c[i] += c[i - 1];
	}
	int hh = 0, tt = 0;
	q[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		while (hh < tt && (dp[q[hh + 1]] - dp[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]]))
		{
			hh++;
		}
		dp[i] = dp[q[hh]] + t[i] * (c[i] - c[q[hh]]) + s * (c[n] - c[q[hh]]);
		while (hh < tt && (dp[q[tt]] - dp[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (dp[i] - dp[q[tt]]) * (c[q[tt]] - c[q[tt - 1]]))
		{
			tt--;
		}
		q[++tt] = i;
	}
	cout << dp[n] << endl;
	return 0;
}

\(T3：\)

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 3e5 + 10;

int n, s;
ll t[N], c[N];
ll dp[N], q[N];

int main()
{
	ios :: sync_with_stdio(0);
	(0), (0);
	cin >> n >> s;
	for (int i = 1; i <= n; i++)
	{
		cin >> t[i] >> c[i];
		t[i] += t[i - 1];
		c[i] += c[i - 1];
	}
	int hh = 0, tt = 0;
	q[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		int l = hh, r = tt;
		while (l < r)
		{
			int mid = (l + r) >> 1;
			if (dp[q[mid + 1]] - dp[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]))
			{
				r = mid;
			}
			else
			{
				l = mid + 1;
			}
		}
		dp[i] = dp[q[r]] + t[i] * (c[i] - c[q[r]]) + s * (c[n] - c[q[r]]);
		while (hh < tt && (dp[q[tt]] - dp[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (dp[i] - dp[q[tt]]) * (c[q[tt]] - c[q[tt - 1]]))
		{
			tt--;
		}
		q[++tt] = i;
	}
	cout << dp[n] << endl;
	return 0;
}

P4655 [CEOI 2017] Building Bridges link

Description

have\(n\)The columns are arranged in sequence, each column has a height. The\(i\)The height of the column is\(h_i\)。

Now if you want to build a number of bridges, if a bridge is in the first\(i\)Root and the\(j\)Between the pillars, then\((h_i-h_j)^2\)The price of .

Before building a bridge, all the unused pillars will be demolished because they will interfere with the process of making the bridge. The\(i\)The cost of the column being removed is\(w_i\),Notice\(w_i\)Not necessarily, because the government may want to remove some pillars.

Now the government wants to know, through the bridge,\(1\)Root and the\(n\)Minimum cost of connecting a column. Note that bridges cannot intersect anywhere outside the endpoint.

Data range

\(2\le n\le 10^5,0\le h_i,\vert w_i\vert\le 10^6\)。

Problem solving

Use first\(w\)prefix and replace the original sequence.

Consider listing first\(O(n^2)\)State transfer equation:

Status indicates:\(dp[i]\)It means using a bridge to hold the front\(i\)Minimum cost of connecting a column.
initialization:\(dp[1]=0\)
State transfer: Consider columns\(i\)and\(j\)Connecting, there are:

\[dp[i]=\min(dp[j]+(h[i]-h[j])^2+w[i-1]-w[j]) \]
Answer:\(dp[n]\)。

Now consider slope optimization, move the term:

\[dp[j]=2h[i]h[j]-h[j]^2-w[j]+dp[i]-h[i]^2+w[i-1] \]

Found out because of the original\(h[i]\)Can\(0\), therefore the horizontal axis\(h[j]\)If it is not strictly increased, you can only use Li Chao line segment tree optimization.

Substitute the formula into:

\[dp[i]=h[i]^2+w[i-1]+\min(-2h[j]h[i]+dp[j]+h[j]^2-w[j]) \]

The problem turns into: inserting a straight line every time\(y=-2h[j]\cdot x+dp[j]+h[j]^2-w[j]\), please\(x=h[i]\)minimum value when .

Use the Li Chao Line to maintain it, time complexity\(O(n\log n)\)。

Code

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n;
long long h[N], w[N];
long long dp[N];

struct line
{
	long long k, b;
	
	inline long long calc(long long x)
	{
		return k * (x - 1) + b;
	}
} p[N];

struct SGT
{
	#define ls x << 1
	#define rs x << 1 | 1
	#define mid ((l + r) >> 1)
	int dat[M << 2];
	
	void update(int x, int l, int r, int k)
	{
		if (!dat[x])
		{
			dat[x] = k;
			return;
		}
		if (p[k].calc(mid) < p[dat[x]].calc(mid))
		{
			swap(k, dat[x]);
		}
		if (p[k].calc(l) < p[dat[x]].calc(l))
		{
			update(ls, l, mid, k);
		}
		if (p[k].calc(r) < p[dat[x]].calc(r))
		{
			update(rs, mid + 1, r, k);
		}
	}
	
	long long query(int x, int l, int r, int k)
	{
		if (r < k || l > k)
		{
			return 1e18;
		}
		long long res = p[dat[x]].calc(k);
		if (l == r)
		{
			return res;
		}
		return min(res, min(query(ls, l, mid, k), query(rs, mid + 1, r, k)));
	}
} t;

int main()
{
	ios :: sync_with_stdio(0);
	(0), (0);
	p[0].b = 1e18;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> h[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> w[i];
		w[i] = w[i] + w[i - 1];
	}
	p[1].k = -2 * h[1], p[1].b = h[1] * h[1] - w[1];
	(1, 1, M, 1);
	for (int i = 2; i <= n; i++)
	{
		dp[i] = h[i] * h[i] + w[i - 1] + (1, 1, M, h[i] + 1);
		p[i].k = -2 * h[i], p[i].b = dp[i] + h[i] * h[i] - w[i];
		(1, 1, M, i);
	}
	cout << dp[n] << endl;
	return 0;
}

P4072 [SDOI2016] Zhengtulink

Description

Pine started\(S\)Arrival\(T\)The journey of the land.

from\(S\)Arrival\(T\)The roads of the land can be divided into\(n\)There is a rest station at the dividing point of two adjacent sections of roads.

Pine plan\(m\)The day arrives\(T\)land. Excluding the\(m\)Outside the sky, Pine must spend the night at the rest stop every night. Therefore, a section of the road must be completed in the same day.

Pine hopes that the length of the road he walks every day is as close as possible, so he hopes that the variance of the length of the road he walks every day is as small as possible.

Help Pine find out what is the minimum variance.

Let the variance be\(v\), can prove that\(v\times m^2\)is an integer. To avoid accuracy errors, output when outputting results\(v\times m^2\)。

Data range

\(1 \le n \le 3000\)。

Guaranteed from\(S\)arrive\(T\)The total distance does not exceed\(3\times 10^4\)。

\(2 \leq m \leq n+1\), the length of each section of the road shall not exceed\(3 \times 10^4\)ofPositive integer。

Problem solving

Consider simplifying the final answer first (\(a\)Indicates the length of each section of the input):

\[s^2=\frac{(\bar a-a_1)^2+(\bar a-a_2)^2+\cdots+(\bar a-a_m)^2}{m} \]

\[s^2=\frac{m\bar a^2-2\bar a(a_1+a_2+\cdots+a_m)+a_1^2+a_2^2+\cdots+a_m^2}{m} \]

\[s^2=\frac{m(\frac{\sum_{i=1}^ma_i}{m})^2-2(\frac{\sum_{i=1}^ma_i}{m})(\sum_{i=1}^ma_i)+\sum_{i=1}^ma_i^2}{m} \]

\[s^2=-\frac{{(\sum_{i=1}^ma_i)}^2}{m^2}+\frac{\sum_{i=1}^ma_i^2}{m} \]

\[s^2\cdot m^2={-(\sum_{i=1}^ma_i)}^2+m\sum_{i=1}^ma_i^2 \]

It is found that the first item on the right is a fixed value, so as long as the second item on the right is the smallest, that is, the problem is converted intoSeeking the smallest square and harmony。

Might as well\(a\)prefix and replace the original sequence.

So dynamic planning started:

Status representation: Since the division of several paragraphs will also affect the answer, two -dimensional representation should be opened,\(dp[i][j]\)Before expressing\(i\)Item division\(j\)The minimum sum of squares of segments.
initialization:\(dp[0][i]=0\)。
State transfer: Let the last section be\(k+1\sim i\), there are:

\[dp[i][j]=\min(dp[k][j-1]+(a[i]-a[k])^2) \]
Answer:\(dp[n][m]\)Just substitute the above formula.

Time complexity\(O(n^3)\)Unable to pass, consider the optimization of slope.

Substitute the formula into:

\[dp[k][j-1]+a[k]^2=2a[i]a[k]+dp[i][j]-a[i]^2 \]

To make\(dp[i][j]\)Smaller, the cut -off distance is smaller, so the optimal decision point forms aLower convex hull。

because\(a[i]\)Strictly increase, soBoth horizontal coordinates and slopes are strictly increased, just apply the first case.

It is worth noting that because this question is two -dimensional, we optimize the first dimension, so you can enumerate the second dimension first, and then run the second dimension, and then run the second dimension, and then run, and then run\(m\)Passive slope optimization.

Time complexity\(O(m\log n)\)。

Code

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 3e3 + 10;

ll n, m;
ll a[N];
ll dp[N][N], q[N];

int main()
{
	ios :: sync_with_stdio(0);
	(0), (0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[i] += a[i - 1];
		dp[i][1] = a[i] * a[i];
	}
	for (int j = 2; j <= m; j++)
	{
		int h = 0, t = 0;
		q[0] = 0;
		for (int i = 1; i <= n; i++)
		{
			while (h < t && (dp[q[h + 1]][j - 1] - dp[q[h]][j - 1] + a[q[h + 1]] * a[q[h + 1]] - a[q[h]] * a[q[h]]) <= 2 * a[i] * (a[q[h + 1]] - a[q[h]]))
			{
				h++;
			}
			dp[i][j] = dp[q[h]][j - 1] + (a[i] - a[q[h]]) * (a[i] - a[q[h]]);
			while (h < t && (dp[q[t]][j - 1] + a[q[t]] * a[q[t]] - dp[q[t - 1]][j - 1] - a[q[t - 1]] * a[q[t - 1]]) * (a[i] - a[q[t]]) >= (dp[i][j - 1] + a[i] * a[i] - dp[q[t]][j - 1] - a[q[t]] * a[q[t]]) * (a[q[t]] - a[q[t - 1]]))
			{
				t--;
			}
			q[++t] = i;
		}
	}
	cout << m * dp[n][m] - a[n] * a[n] << endl;
	return 0;
}

P4027 [NOI2007] Currency Exchangelink

Description

Xiao Y recently worked in a stock exchange. The stock exchange only issues two types of gold vouchers: A commemorative voucher (hereinafter referred to as A voucher) and B commemorative voucher (hereinafter referred to as B voucher). Every customer holding a voucher has his or her own account. The number of vouchers can be a real number.

As the market fluctuates every day, both types of gold coupons have their own value at that time, that is, the number of RMB that each unit of gold coupon can be exchanged on the same day. We record the\(K\)The value of the A coupon and B vouchers of the sky is\(A_K\)and\(B_K\)(yuan/unit gold coupon).

To facilitate customers, the stock exchange provides a very convenient trading method: proportional trading method.

The proportional trading method is divided into two aspects:

a) Selling voucher: Customer provides one\([0, 100]\)Real numbers within\(OP\)As a selling ratio, its meaning is:\(OP\%\)A voucher and\(OP\%\)The B voucher of the time is exchanged for RMB;

b) Buy coupons: Customer pays\(IP\)RMB, the exchange will exchange to the user for the total value\(IP\)The ratio of gold vouchers to meet the A vouchers and B vouchers provided to customers is in the\(K\)The sky happened to be\(\mathrm{Rate}_ K\)；

For example, suppose next\(3\)In the day\(A_K,B_K,\mathrm{Rate}_ K\)The changes are:

time	\(A_K\)	\(B_K\)	\(\mathrm{Rate}_ K\)
First day	\(1\)	\(1\)	\(1\)
the next day	\(1\)	\(2\)	\(2\)
Third day	\(2\)	\(2\)	\(3\)

Assume that on the first day, the user has\(100\)Yuan RMB but no vouchers.

Users can perform the following operations:

time	User operation	RMB (yuan)	A Quantity of coupons	Number of coupons
Open an account	none	\(100\)	\(0\)	\(0\)
First day	Buy\(100\)Yuan	\(0\)	\(50\)	\(50\)
the next day	Sell\(50\%\)	\(75\)	\(25\)	\(25\)
the next day	Buy\(60\)Yuan	\(15\)	\(55\)	\(40\)
Third day	Sell\(100\%\)	\(205\)	\(0\)	\(0\)

Note that multiple operations can be performed within the same day.

Xiao Y is a very economical employee. Through long-term operation and market calculations, he already knows the future.\(N\)The value of A and B vouchers within the day and\(\mathrm{Rate}\)Essence He also hopes to be able to calculate if he had\(S\)Yuan, then\(N\)How much can the queen get at most?

Data range

\(N \le 10^5\)，\(0 < A_K \leq 10\)，\(0 < B_K\le 10\)，\(0 < \mathrm{Rate}_K \le 100\)，\(\mathrm{MaxProfit} \leq 10^9\)。

There must be an optimal trading solution to satisfy:

After each buy operation, use all the RMB, and sell all the vouchers for each sell operation.

Problem solving

Consider DP.

Status indicates:\(dp[i]\)Before expressing\(i\)How much money can you get in the day?
initialization:\(dp[0]=S\)。
Status transfer: Let's say it's now\(i\)God, to make money at most, you must not buy a voucher.
- Don't sell gold coupons:\(dp[i]=dp[i-1]\)。
- Selling gold coupons: Let the gold coupons sold now are in the\(j\)If you buy it, if you sell profits, you should spend all the money to buy vouchers to obtain the maximum benefits.
  
  Set a first\(i\)Heaven can get at most\(x_i\)open\(A\)Coupon,\(y_i\)open\(B\)Coupons include:
  
  \[x_i=dp_i\frac{R_i}{A_iR_i+B_i} \]
  
  \[y_i=dp_i\frac{1}{A_iR_i+B_i} \]
  
  so:\(dp[i]=\max(x_jA_i+y_jB_i)\)。
In summary, the state transition equation is:

\[dp[i]=\max(dp[i-1],\max(x_jA_i+y_jB_i)) \]
Answer:\(dp[n]\)。

Now let’s consider slope optimization, and we turn it into an equation that can be processed by slope optimization (not considering it first, and then count it in the end):

\[y_j=-\frac{A_i}{B_i}x_j+\frac{1}{B_i}dp[i] \]

Discover\(x_j\)There is no monotonous, so consider using the Li Chao Line Tree.

Deformed to:

\[dp[i]=b[i]\max(x_j\frac{a_i}{b_i}+y_j) \]

The problem turns into: inserting a straight line every time\(y=x_j\cdot x+y_j\), please\(x=\frac{a_i}{b_i}\)maximum value when .

Use the Li Chao Line to maintain it, time complexity\(O(n\log n)\)。

It is worth noting that this question requires querying the minimum value of the real number position, which can be discrete, and then the Li Chao line segment tree isclac()Just rewrite the function.

Code

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 1e5 + 10;
const double eps = 1e-10;

int n;
double a[N], b[N], c[N], d[N], r[N];
double ans;

struct line
{
	double k, b;
	int id;
	
	inline double calc(int x)
	{
		return k * c[x] + b;
	}
} p[N];

struct SGT
{
	#define ls x << 1
	#define rs x << 1 | 1
	#define mid ((l + r) >> 1)
	int dat[N << 2];
	
	void update(int x, int l, int r, int k)
	{
		if (!dat[x])
		{
			dat[x] = k;
			return;
		}
		if (p[k].calc(mid) - p[dat[x]].calc(mid) > eps)
		{
			swap(k, dat[x]);
		}
		if (p[k].calc(l) - p[dat[x]].calc(l) > eps || (p[k].calc(l) == p[dat[x]].calc(l) && k < dat[x]))
		{
			update(ls, l, mid, k);
		}
		if (p[k].calc(r) - p[dat[x]].calc(r) > eps || (p[k].calc(r) == p[dat[x]].calc(r) && k < dat[x]))
		{
			update(rs, mid + 1, r, k);
		}
	}
	
	double query(int x, int l, int r, int k)
	{
		if (r < k || l > k)
		{
			return 0;
		}
		double res = p[dat[x]].calc(k);
		if (l == r)
		{
			return res;
		}
		return max(res, max(query(ls, l, mid, k), query(rs, mid + 1, r, k)));
	}
} t;

int main()
{
	ios :: sync_with_stdio(0);
	(0), (0);
	cin >> n >> ans;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i] >> b[i] >> r[i];
		c[i] = d[i] = a[i] / b[i];
	}
	sort(c + 1, c + n + 1);
	for (int i = 1; i <= n; i++)
	{
		int sum = lower_bound(c + 1, c + n + 1, d[i]) - c;
		ans = max(ans, b[i] * (1, 1, n, sum));
		p[i].k = ans * r[i] / (a[i] * r[i] + b[i]), p[i].b = ans / (a[i] * r[i] + b[i]);
		(1, 1, n, i);
	}
	cout << fixed << setprecision(3) << ans << endl;
	return 0;
}