Nâng Cấp Vũ Khí Có Bảo Hiểm Bậc
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Trong một trò chơi nhập vai, người chơi muốn nâng cấp thanh kiếm từ cấp $0$ lên cấp $N$. Khi đang ở cấp $i$ ($0 \le i < N$), mỗi lần đập đá tốn $W_i$ vàng và có xác suất thành công là $P_i / 100$ (lên cấp $i+1$). Nếu thất bại (xác suất $1 - P_i / 100$), nhờ bùa bảo hiểm bậc nên thanh kiếm chỉ bị tụt về cấp $B_i$ ($0 \le B_i \le i$). Hãy tính kỳ vọng tổng số vàng cần chi để nâng cấp thanh kiếm từ cấp $0$ lên cấp $N$ theo modulo $10^9 + 7$.
Dữ liệu vào
Dòng 1 chứa số nguyên $N$ ($1 \le N \le 2000$). $N$ dòng tiếp theo, dòng thứ $i$ (ứng với cấp $i-1$, đánh số từ $0$ đến $N-1$) gồm 3 số nguyên $P_i, B_i, W_i$ ($1 \le P_i \le 100, 0 \le B_i \le i, 1 \le W_i \le 10^6$).
Dữ liệu ra
In ra kỳ vọng tổng số vàng theo modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 3 100 0 10 50 0 20 50 1 30 |
170 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion