Tổng ô đi qua (MOVSUM)
Đề bài
Bờm có một bảng kích thước $1 \times N$ chia thành $N$ ô vuông được đánh số $1, 2, \ldots, N$ từ trái sang phải. Trên ô có chỉ số $i$ ghi số nguyên $a_i$.
Bờm chơi trò chơi di chuyển hai quân cờ trên bảng này. Quân cờ bên trái có màu xanh, ban đầu đặt ở ô 1, quân cờ bên phải có màu đỏ, ban đầu đặt ở ô $N$. Bờm có thể di chuyển bất kì quân cờ nào, số lần tuỳ ý, miễn là tuân thủ các quy tắc sau:
- Quân cờ xanh chỉ có thể di chuyển sang phải (tức là đến ô có chỉ số lớn hơn chỉ số ô hiện tại).
- Quân cờ đỏ chỉ có thể di chuyển sang trái (tức là đến ô có chỉ số nhỏ hơn chỉ số ô hiện tại).
- Mỗi bước di chuyển chỉ có thể dịch quân cờ qua số ô là một trong $K$ số $s_1, s_2, \ldots, s_K$.
- Hai quân cờ không thể đứng trên cùng một ô, cũng không thể vượt qua nhau (tức là quân cờ xanh không thể di chuyển đến ô chỉ số lớn hơn hoặc bằng chỉ số của ô chứa quân cờ đỏ, và ngược lại).
Điểm Bờm nhận được trong trò chơi bằng tổng các số trong các ô mà các quân cờ đã đứng (kể cả hai ô xuất phát). Hãy giúp Bờm tính toán xem tổng điểm lớn nhất có thể đạt được là bao nhiêu.
Dữ liệu:
- Dòng 1: hai số nguyên $N, K$ $(1 < N \le 10^5;\ 1 < K \le 10^3)$.
- Dòng 2: $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(-10^3 \le a_i \le 10^3)$.
- Dòng 3: $K$ số nguyên $s_1, s_2, \ldots, s_K$ $(1 \le s_i \le N - 1)$.
Kết quả: một số nguyên là tổng điểm lớn nhất có thể đạt được.
Subtask: 20% điểm đầu tiên với $N, K \le 10$; 30% điểm tiếp theo với $N \le 10^4$; 50% điểm còn lại với $N \le 10^5$.
9 2
3 2 6 6 0 2 4 5 5
3 224Minh hoạ ví dụ: ô xanh là các ô quân xanh đã đứng, ô đỏ là các ô quân đỏ đã đứng.
Quân xanh đi $1 \to 3$ (bước 2), quân đỏ đi $9 \to 7 \to 4$ (bước 2 rồi bước 3). Tổng điểm $= (3 + 6) + (5 + 4 + 6) = 24$.
Lời mở đầu
Thoạt nhìn bài có vẻ rắc rối vì 2 quân cờ di chuyển xen kẽ, không được vượt nhau. Nhưng chỉ cần một nhận xét nhỏ là bài tách thành hai bài quy hoạch động độc lập rất quen thuộc, rồi ghép lại bằng kỹ thuật max tiền tố. Mình đi lần lượt: vét cạn (subtask 1) → quy hoạch động + thử mọi cặp (subtask 2) → thêm max tiền tố (full điểm), mỗi cách đều nộp thử trên bộ test thật.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | $N$ | $K$ | $a_i$ | $s_i$ lớn nhất | Đáp án |
|---|---|---|---|---|---|
| 001–020 | 3 – 10 | 2 – 10 | -20 → 20 | 9 | -25 → 47 |
| 021–050 | 10.000 – 10.000 | 1.000 – 1.000 | -999 → 999 | 9.999 | 158.390 → 928.578 |
| 051–100 | 100.000 – 100.000 | 1.000 – 1.000 | -999 → 999 | 32.768 | 251.565 → 4.304.919 |
Bộ test khớp đúng 3 subtask của đề: 20 test đầu $N, K \le 10$; 30 test tiếp theo $N = 10^4$; 50 test cuối $N = 10^5$ (tất cả test lớn đều có $K = 1000$). Một vài điểm cần lưu ý:
- Các bước $s_i$ có thể trùng nhau (95 test). Không sao cả, chỉ là thử lại một bước đã thử.
- Đáp án có thể âm (6 test nhỏ): hai quân cờ đứng yên vẫn bị tính 2 ô xuất phát, mà 2 ô đó có thể âm. Vậy đừng khởi tạo đáp án bằng 0.
- Có những ô không tới được (ví dụ mọi bước đều chẵn thì quân xanh chỉ tới các ô lẻ). Phải đánh dấu riêng các ô này, không được coi tổng của chúng là 0.
- Đáp án lớn nhất cỡ $4{,}3 \cdot 10^6$ nên
intcũng đủ, nhưng mình vẫn dùnglong longcho an toàn.
| Subtask | Điều kiện | Test | Cách 1 vét cạn | Cách 2 QHĐ + thử mọi cặp | Cách 3 QHĐ + max tiền tố |
|---|---|---|---|---|---|
| 1 (20%) | $N, K \le 10$ | 001–020 | qua | qua | qua |
| 2 (30%) | $N \le 10^4$ | 021–050 | quá thời gian | qua | qua |
| 3 (50%) | $N \le 10^5$ | 051–100 | quá thời gian | quá thời gian | qua |
Ý tưởngTách thành 2 quân đi riêng, ghép ở chỗ dừng
Nhận xét quan trọng: gọi $i$ là ô cuối cùng quân xanh dừng, $j$ là ô cuối cùng quân đỏ dừng. Mọi ô quân xanh từng đứng đều $\le i$, mọi ô quân đỏ từng đứng đều $\ge j$. Nếu $i < j$ thì ta cứ đi hết quân xanh trước rồi mới đi quân đỏ – không bao giờ có chuyện đụng hay vượt nhau. Vậy luật "không vượt nhau" chỉ còn là điều kiện $i < j$, còn 2 quân đi hoàn toàn độc lập.
$g[j]$ = tổng lớn nhất khi quân đỏ đi từ ô $N$ và dừng ở ô $j$: $g[N] = a_N$, $g[j] = a_j + \max_t g[j + s_t]$.
(Ô không tới được thì $f$ hay $g$ bằng $-\infty$.) Đáp án $= \max_{i < j} \big(f[i] + g[j]\big)$.
Tính $f$ và $g$ mất $O(NK)$. Phần ghép: thay vì thử mọi cặp $(i, j)$ – $O(N^2)$ – ta duyệt $j$ từ trái sang phải và giữ best = max(f[1..j−1]), mỗi bước chỉ cập nhật thêm $f[j-1]$. Khi đó đáp án $= \max_j (\text{best} + g[j])$, chỉ $O(N)$.
Em nhập dữ liệu rồi bấm Tiếp để xem 3 giai đoạn: tính $f$ (xanh), tính $g$ (đỏ), rồi quét max tiền tố:
Cách 1Vét cạn mọi đường đi của từng quân
Dùng nhận xét trên, ta liệt kê mọi đường đi của quân xanh (ô dừng, tổng điểm) bằng đệ quy, tương tự với quân đỏ, rồi thử mọi cặp có ô dừng xanh < ô dừng đỏ.
xanh, doo lớn dần theo số đường đi.Kết quả chạy thật: đúng 20/100 test – quá thời gian test 021–100. Số đường đi tăng theo cấp số nhân, $N = 10^4$ là "chết" ngay.
Cách 2Quy hoạch động f, g rồi thử mọi cặp
Thay vì liệt kê từng đường, mỗi ô chỉ cần nhớ tổng lớn nhất để dừng ở đó: chính là $f[i]$ và $g[j]$. Sau đó thử mọi cặp $i < j$.
NEG = -1e18đánh dấu ô không tới được. Phải kiểm tra!= NEGtrước khi cộng, nếu không $-10^{18} + 999$ sẽ thành một số "hợp lệ" nhầm.ftính từ trái sang phải (ô $i - s_t$ đã tính trước),gtính từ phải sang trái (ô $j + s_t$ đã tính trước).
Kết quả chạy thật: đúng 50/100 test – quá thời gian test 051–100. Với $N = 10^5$ phần thử cặp tốn $5 \cdot 10^9$ phép tính nên quá thời gian.
Cách 3Thêm max tiền tố – full điểm
Giữ nguyên phần tính $f$, $g$; chỉ thay 2 vòng lặp thử cặp bằng 1 vòng quét $j$ với biến best.
bestđược cập nhật bằngf[j - 1]trước khi dùng, nên luôn bằng $\max(f[1..j-1])$ – đúng điều kiện $i < j$.- Tổng thời gian $O(NK + N)$: với $N = 10^5$, $K = 10^3$ là $2 \cdot 10^8$ phép tính đơn giản, C++ chạy chưa tới nửa giây (đo thật chậm nhất 0,45 giây khi máy đang bận).
Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,448 giây.
Bản Python (mình viết thêm, chấm trên cùng bộ test): cách 1 được 20/25 test – quá thời gian test 021–025 (mình chỉ chạy thử test 001–025 vì các test lớn hơn chắc chắn quá thời gian); cách 2 được 20/28 test – quá thời gian test 021–025, 051–053 (mình chỉ chạy thử test 001–025, 051–053 vì các test lớn hơn chắc chắn quá thời gian); cách 3 được 20/28 test – quá thời gian test 021–025, 051–053 (mình chỉ chạy thử test 001–025, 051–053 vì các test lớn hơn chắc chắn quá thời gian). Phần tính $f$, $g$ tốn $N \cdot K$ phép tính: $10^7$ ở subtask 2 và $10^8$ ở subtask 3 – quá sức Python trong 1 giây, nên bản Python chỉ ăn được subtask 1; muốn full điểm thì nộp C++.
Nhận xét
Đăng nhận xét