Nâng Cấp Vũ Khí Có Bảo Hiểm Bậc

Buổi 51 — Probability DP Dynamic Programming
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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.

Draft saved