当前位置：网站首页>AcWing 300. Task arrangement

AcWing 300. Task arrangement

2022-07-02 16:31:00 【superhuanghai】

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

       
        #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.