Subtask 1 (30%) : ~N \le 20~

Ta sinh ~2^{n}~ trường hợp có thể chọn và tính toán trong ~\mathcal {O}(N)~

Độ phức tạp: ~\mathcal {O}(N \times2^{n})~

Subtask 2 (25%): ~N \le 5000~

Ở Subtask này ta có thể quy hoạch động với độ phứt tạp ~\mathcal {O}(N^{2})~

Gọi ~dp_i~ là kết quả tối ưu nhất cho các cách chọn từ ~1~ -> ~i~ và có chọn công việc ~i~

• ~dp_i = b_i~ nếu chỉ chọn duy nhất công việc ~i~
• ~dp_i = max(dp_i,\ dp_j + b_i + (a_i-a_j)\times d_j)~ với ~j+t_j-1 < i~ Độ phức tạp: ~\mathcal {O}(N^{2})~

int ans = 0;
FOR (i, 1, n){
    dp[i] = b[i];
    FORD(j, i-1, 1){
        if (j+t[j]-1 >= i) continue;
        maximize(dp[i], dp[j] + b[i] + (a[i]-a[j])*d[j]);
    }
    maximize(ans, dp[i]);
}
cout << ans ;

Subtask 3 (25%) : ~a_i = 1, \ \forall i \in [1, N]~

Nhận xét: vì ~a_1 = a_2 = ... = a_n~ nên công thức quy hoạch động lúc này chỉ còn:

• ~dp_i = b_i~ nếu chỉ chọn duy nhất công việc ~i~
• ~dp_i = max(dp_i,\ dp_j + b_i)~ với ~j+t_j-1 < i~.

Đặt ~best~ là giá trị ~dp_j~ lớn nhất thoã mãn ~j+t_j-1 < i~, ta chỉ cần cập nhật ~best~ duy nhất ~N~ lần, lúc này có thể tính nhanh trong ~\mathcal {O}(1) \ dp_i = best + b_i~

int best = 0, ans = 0;
for (int i = 1; i <= n; i++){
    dp[i] = best + b[i];
    W[i+t[i]-1].push_back(i);
    for (int x : W[i]){
        best = max(best, dp[x]);
    }
    ans = max(ans, dp[i]);
}
cout << ans;

Subtask 4, 5 : Giới hạn đề bài

Quay trở lại với Subtask 3, ta có công thức tổng quát là :

• ~dp_i = max(b_i,\ dp_j + b_i + (a_i-a_j)\times d_j)~ với ~j+t_j-1 < i~

Khai triển biểu thức trên ta được:

• ~dp_i = b_i + max(a_i \times d_j + dp_j - a_j\times d_j)~ với ~j+t_j-1 < i~

Đặt ~A = d_j, B = dp_j - a_j\times d_j~ có thể đưa biểu thức về dạng phương trình đường thẳng ~f(x) = Ax + B~. Đến đây ta cần tìm ~f(a_i)~ lớn nhất bằng cách sử dụng Convex Hull Trick, IT đoạn thẳng, Lichao Tree .

Độ phức tạp: ~\mathcal {O}(N \times log_{2}N)~