Jump to the question with one click
Question description
There are $n$ tasks that need to be processed on the machine, which form a sequence. The tasks are numbered $1$ to $n$, so the sequence is arranged as $1, 2, 3 \cdots n$. These $n$ tasks are divided into several batches, and each batch contains several adjacent tasks. Starting from time $0$, these tasks are processed in batches, and the time required to complete the ii-th task alone is $T_i$. Before each batch of tasks starts, the machine needs to start up time $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 time. The cost of each task is its completion time multiplied by a cost coefficient $C_i$. Please determine a grouping plan that minimizes the total cost.
Input format
The first line is an integer $n$. The second line contains an integer $s$. The next $n$ lines, each line has a pair of integers, $T_i$ and $C_i$ respectively, indicating that the time required to complete the ii-th task alone is $T_i$ and its cost coefficient $C_i$.
Output format
One line, one integer, representing the minimum total cost.
Input and output samples
Input #1
5
1
1 3
3 2
4 3
2 3
1 4Output #1
153Instructions/Tips
For $100\%$ data, $1 \le n \le 3 \times 10^5$ , $1 \le s \le 2^8$ , $\left| T_i \right| \le 2^8$ , $0 \le C_i \le 2^8$ .
Ideas (Note: There is a complete AC code at the end, be sure to read to the end!!!)
Obviously, the maximum value of $n$ is $3 \times 10^5$, and violence will inevitably explode.
So what is "slope optimization"?
Answer: Use linear programming to optimize the dp formula.
As the name suggests, slope dp is to convert the information given in the question into the coordinate system and determine the slope to solveThat’s it for the train of thought. , this idea seems very abrupt at first glance, so let’s analyze it in detail.
First of all, we can get this dp formula based on the proposal:
dp[i] = min(dp[i], dp[j] + tm[i] (fm[i] – fm[j]) + (fm[n] – fm[j]) s);
Among them, $dp_i$ is used to record the optimal solution up to point $i$, $tm_i$ records the prefix sum of $t$ array up to $i$, $f_i$ is the same, point $j$ is just the middle one Split point, $tm_i\times(fm_i-fm_j)$ is to find the total time spent in this interval. The last formula is very important. We have already divided it once at $i$, then we can directly accumulate the following The $s$ of the node (the time it takes to start the machine) is $(fm_n-fm_j)\times s$,This idea is something that even an individual can understand.
So far we can get:
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
dp[i] = min(dp[i], dp[j] + tm[i] * (fm[i] - fm[j]) + (fm[n] - fm[j]) * s);
}
}The code written in this way can get 20 points in Luogu, and all other points will be lost.
Obviously, anyone who has studied dp can see that this code is just an ordinary linear dp, so next we will use this code to derive the slope dp code.
Through the above dynamic transfer equation we can deduce:
dp[i]=dp[j]-(tm[i]+s)fm[j]+tm[i]fm[i]+fm[n]*s;
It’s just a matter of disassembling and merging similar items, and even primary school students can figure it out.
Anyone who has studied slope dp can find that this formula conforms to the basic form of the function: $y=kx+b$, we regard (tm[i]+s) as k, and the remaining terms as b, that is, It can be concluded that the slope of this function is (tm[i]+s)
In this way, we can deduce: for each $i$, we can regard dp[i] as the ordinate of this node, and fm[i] as the coordinate of this point, so we can put each point into the coordinate Department (not a sample sketch, it’s a bit ugly, let’s take a look at it):
Then we bring the function image into the coordinate system
For this dp[i]=dp[j]-(tm[i]+s)fm[j]+tm[i]For the function image of fm[i]+fm[n]*s, if you want the optimal dp solution of the ball, you need to see which point the function image hits first, but if you want to compare each point in each image, then It takes too much time, so here we will use the knowledge of slope
The points connected by the red line are the points that need to be judged, and the blue ones above are the points that do not need to be judged.
Obviously tan∠ACD > tan∠BCD(Haven’t learned tan clicks on links）
So to determine the slope between two points, we only need to determine the value of the diagonal side/hypotenuse ($CD=x_c-x_c$, $BD=y_b-y_d$). Here we can use a queue to maintain these point (this operation code is very detailed), so for each $i$, the value of each tan in the queue must be = the value of tan (current point). However, the value <= tan (current point) will be kicked out directly. Queue, because there is no need to compare, so now we can get the code after slope optimization:
for (int i = 1; i <= n; ++i) {
int j = 0;
while (l < r && dp[qu[l + 1]] - dp[qu[l]] <= (tm[i] + s) * (fm[qu[l + 1]] - fm[qu[l]]))
l++;
j = qu[l];
//dp[i] = min(dp[i], dp[j] - (s + tm[i]) * fm[j] + tm[i] * fm[i] + s * fm[n]);
dp[i] = dp[qu[l]] - (s + tm[i]) * fm[qu[l]] + tm[i] * fm[i] + s * fm[n];
//while(l<r&&)
while (l < r && (dp[qu[r]] - dp[qu[r - 1]])* (fm[i] - fm[qu[r]]) >= (dp[i] - dp[qu[r]]) * (fm[qu[r]] - fm[qu[r - 1]]))
r--;
qu[++r] = i;
}*Note: The judgment in the code is usedis to prevent floating point operations**
However, if you use this method, you will find that you can only pass $60\%$ points, and the rest of the points are all WA. However, in our previous push, we ignored and the ordinate (the specific value of the ordinate has been mentioned before) is a negative number. Condition
As shown in the figure, point E will cause the comparison to be out of control when looking for the nearest point. Therefore, in the first while loop, we switch to the dichotomy idea. The overall idea is the same as before, and we directly enter the code:
int bs(int ll, int rr, int ss) {//求j
int mid;
int res=qu[r];
while (ll <= rr) {
//l++;
mid = (ll + rr) / 2;
if (dp[qu[mid + 1]] - dp[qu[mid]] >= ss * (fm[qu[mid + 1]] - fm[qu[mid]])) {
res = qu[mid];
rr = mid - 1;
}
else
ll = mid + 1;
}
return res;
}The oiers who see this probably already understand it. If you still don’t understand it, you can understand it with the complete code:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#pragma warning(disable:4996)
using namespace std;
#define int long long
int n, s, tm[1000010], fm[1000010], ans = 0x3f3f3f3f, dp[1000010], qu[1000010], l, r=0;
struct node
{
int t, f;
}edge[1000010];
int bs(int ll, int rr, int ss) {
int mid;
int res=qu[r];
while (ll <= rr) {
//l++;
mid = (ll + rr) / 2;
if (dp[qu[mid + 1]] - dp[qu[mid]] >= ss * (fm[qu[mid + 1]] - fm[qu[mid]])) {
res = qu[mid];
rr = mid - 1;
}
else
ll = mid + 1;
}
return res;
}
signed main() {
scanf("%lld%lld", &n, &s);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &edge[i].t, &edge[i].f);
tm[i] = tm[i - 1] + edge[i].t;
fm[i] = fm[i - 1] + edge[i].f;
}
memset(dp, 0x3f3f3f3f, 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] + tm[i] * (fm[i] - fm[j]) + (fm[n] - fm[j]) * s);
}
}*/
//dp[i]=dp[j]-(tm[i]+s)*fm[j]+tm[i]*fm[i]+fm[n]*s;
qu[l] = 0;
qu[++r] = 0;
for (int i = 1; i <= n; ++i) {
int j = bs(l, r, (tm[i] + s));
dp[i] = dp[j] + tm[i] * (fm[i] - fm[j]) + s * (fm[n] - fm[j]);
while (l < r && (dp[qu[r]] - dp[qu[r - 1]])* (fm[i] - fm[qu[r]]) >= (dp[i] - dp[qu[r]]) * (fm[qu[r]] - fm[qu[r - 1]]))
r--;
qu[++r] = i;
}
cout << dp[n];
return 0;
}All oiers who read to the end, give it a thumbs up qwq
