AcWing 300. Task arrangement

One 、 Sample explanation

Examples ：

5 A mission , The start time of each task is 1

1 3 4 2 1

3 2 3 3 4

If we put the front 3 Treat a task as a batch , after 2 Treat a task as a batch .

that

The first batch of time points ：1+3+4=8 It takes 8 Time , Plus the start time of a batch 1, It's a total of 9 Time

Time point of the second batch ：2+1=3 It takes 3 Time , Plus the start time of a batch 1, Namely 4 Time , So the second time point is 9+4=13

Next, calculate the cost :

The total cost of the first batch is 3+2+3=8 The total cost is 8*9=72

The total cost of the second batch is 3+4=7 7*13=91

72+91=163

The optimal solution is 153, It seems that this division is not the optimal solution , good , Finished understanding the topic .

Two 、 Their thinking

Use The cost is calculated in advance Thought , Consider the subtasks of the current batch , Required startup time \(S\), The start time will be accumulated to the completion time of all tasks after this .

State definition

\(f[i]\) I'll go ahead \(i\) The minimum cost of dividing a task into several batches

Transfer equation

\(f[i]=min(f[j]+sumT[i]*(sumC[i]-sumC[j])+S*(sumC[N]-sumC[j])\)

Among them the first \(j+1\) to \(i\) Tasks are completed in the same batch

Algorithm design

Set double cycle , The time complexity is \(O(N^2)\)

loop 1: Set subbatch to \(i\) Tasks end

loop 2: Set subbatch to \(j\) Task is to start , among \(0<j<i-1\)

\(f[i]=min(f[i]\), Transfer equation calculation results )

3、 ... and 、 Implementation code

Log in and copy

       

        #include <bits/stdc++.h>
        

        
using namespace std;
        
typedef long long LL;
        
const int N = 5010;
        

        
int n;
        
LL s;      // Waiting time 
        
LL sc[N];  // Each task has a cost , use c[i] To express ,sc[i] It's the prefix and 
        
LL st[N];  // Each task has its own execution time t[i], The prefix and are st[i]
        
LL f[N];
        

        
int main() {
        
    // Optimize input 
        
    ios::sync_with_stdio(false);
        
    cin >> n >> s;
        
    for (int i = 1; i <= n; i++) {
        
        LL t, c;
        
        cin >> t >> c;
        
        st[i] = t + st[i - 1];
        
        sc[i] = c + sc[i - 1];
        
    }
        

        
    // initialization 
        
    memset(f, 0x3f, sizeof f);
        
    f[0] = 0;
        

        
    //n^2 The time complexity of the 
        
    for (int i = 1; i <= n; i++)
        
        for (int j = 0; j < i; j++)
        
            f[i] = min(f[i], f[j] + st[i] * (sc[i] - sc[j]) + s * (sc[n] - sc[j]));
        
    // Output 
        
    printf("%lld\n", f[n]);
        
    return 0;
        
}
       
       

        
1.
        
2.
        
3.
        
4.
        
5.
        
6.
        
7.
        
8.
        
9.
        
10.
        
11.
        
12.
        
13.
        
14.
        
15.
        
16.
        
17.
        
18.
        
19.
        
20.
        
21.
        
22.
        
23.
        
24.
        
25.
        
26.
        
27.
        
28.
        
29.
        
30.
        
31.
        
32.
        
33.
        
34.
        
35.