Hướng dẫn giải của Tàu điện
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Từ ga ~i~ (mua vé ~c_i~) tàu chỉ xuống được ở các ga ~i + l_i, \dots, i + r_i~. Cần tính tổng tiền vé của tất cả các hành trình khác nhau từ ga 1 đến ga ~N~, lấy dư cho ~10^9 + 7~. Hai hành trình khác nhau khi có ít nhất một ga khác nhau.
Sub 1: Vét cạn bằng DFS — dùng khi ~N \le 20~
Từ ga ~u~, thử mọi ga ~v~ trong đoạn cho phép (không vượt quá ~N~); khi đến ga ~N~ cộng tổng vé của hành trình. Số hành trình tối đa khoảng ~2^{N}~. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Quy hoạch động — ~O(N^2)~, dùng khi ~N \le 2000~
Gọi ~ways[j]~ là số hành trình từ ga 1 đến ga ~j~ và ~sum[j]~ là tổng tiền vé của các hành trình đó. Từ ga ~i~ đi tới ga ~j~ thì ~ways[j]~ tăng thêm ~ways[i]~, ~sum[j]~ tăng thêm ~sum[i] + c_i \cdot ways[i]~ (mỗi hành trình đến ~i~ trả thêm ~c_i~). Nếu chỉ nộp sub này: đúng 15/20 test.
Sub 3: Mảng hiệu — ~O(N)~
Cập nhật trên đoạn ga ~[i + l_i, \min(N, i + r_i)]~ được làm bằng mảng hiệu cho cả ~ways~ và ~sum~, nên duyệt các ga từ trái sang phải với ~O(1)~ mỗi ga. Chú ý nhân ~c_i~ với ~ways[i]~ lấy dư cho khỏi tràn số, các ga vượt quá ~N~ bị bỏ qua; ~i + l_i~ có thể tới ~2 \cdot 10^9~ nên tính bằng long long. Dữ liệu vào tới khoảng 24MB nên đọc số bằng fread cho nhanh (đọc bằng scanf có thể bị quá thời gian). Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; ~N \le 20~ gọi sub1, ~N \le 2000~ gọi sub2, còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int n;
long long c[1000005];
long long L[1000005], R[1000005]; // i + l_i có thể vượt N (tới 2.10^9) nên dùng long long
// Đọc số nhanh bằng fread (input tới ~24MB, scanf/cin có thể chậm)
static char buf[1 << 16];
int bufLen = 0, bufPos = 0;
inline int readChar() {
if (bufPos == bufLen) { bufLen = fread(buf, 1, sizeof(buf), stdin); bufPos = 0; if (bufLen <= 0) return -1; }
return buf[bufPos++];
}
inline long long readLL() {
int ch = readChar();
while (ch != -1 && (ch < '0' || ch > '9')) ch = readChar();
long long x = 0;
while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = readChar(); }
return x;
}
// Sub 1: vét cạn - DFS mọi hành trình từ ga 1 đến ga N, dùng khi N <= 20
long long total1;
void dfs(int u, long long cost) {
if (u == n) { total1 = (total1 + cost) % MOD; return; }
for (long long v = u + L[u]; v <= min((long long)n, u + R[u]); v++) dfs(v, cost + c[u]);
}
void sub1() {
total1 = 0;
dfs(1, 0);
printf("%lld\n", total1 % MOD);
}
// Sub 2: quy hoạch động O(N^2), dùng khi N <= 2000
// ways[j] = số cách đến ga j; sum[j] = tổng tiền vé của các cách đó
void sub2() {
vector<long long> ways(n + 2, 0), sum(n + 2, 0);
ways[1] = 1;
for (int i = 1; i < n; i++)
for (long long j = i + L[i]; j <= min((long long)n, i + R[i]); j++) {
ways[j] = (ways[j] + ways[i]) % MOD;
sum[j] = (sum[j] + sum[i] + c[i] % MOD * ways[i]) % MOD;
}
printf("%lld\n", sum[n] % MOD);
}
// Sub 3: giống sub 2 nhưng cộng dồn trên đoạn bằng mảng hiệu, O(N)
void sub3() {
vector<long long> dw(n + 3, 0), ds(n + 3, 0); // mảng hiệu của ways và sum
long long w = 0, s = 0;
for (int i = 1; i <= n; i++) {
w = (w + dw[i]) % MOD;
s = (s + ds[i]) % MOD;
long long wi = (i == 1 ? 1 : w), si = (i == 1 ? 0 : s);
if (i == n) { printf("%lld\n", si); return; }
long long add = (si + c[i] % MOD * wi) % MOD;
long long lo = i + L[i], hi = min((long long)n, i + R[i]);
if (lo > hi) continue;
dw[lo] = (dw[lo] + wi) % MOD; dw[hi + 1] = (dw[hi + 1] - wi + MOD) % MOD;
ds[lo] = (ds[lo] + add) % MOD; ds[hi + 1] = (ds[hi + 1] - add + MOD) % MOD;
}
}
int main() {
freopen("METRO.INP", "r", stdin);
freopen("METRO.OUT", "w", stdout);
n = readLL();
for (int i = 1; i <= n; i++) c[i] = readLL();
for (int i = 1; i <= n; i++) { L[i] = readLL(); R[i] = readLL(); }
if (n <= 20) sub1();
else if (n <= 2000) sub2();
else sub3();
return 0;
}
Bình luận